EasyBlind75DPBit Manipulation

Counting Bits

Given an integer n, return an array ans of length n + 1 such that for each i, ans[i] is the number of 1's in the binary representation of i.

Examples

Input
n = 2
Output
[0,1,1]

0 -> 0 ones, 1 -> 1 one, 2 -> 1 one.

Input
n = 5
Output
[0,1,1,2,1,2]

0->0, 1->1, 2->1, 3->2, 4->1, 5->2.

Constraints

  • •0 <= n <= 10^5

Approaches

Count bits for each number independently.

CodeT: O(n * 32) = O(n) | S: O(n)
def count_bits(n):
    result = []
    for i in range(n + 1):
        count = 0
        num = i
        while num:
            count += num & 1
            num >>= 1
        result.append(count)
    return result

Use the relation: dp[i] = dp[i >> 1] + (i & 1).

CodeT: O(n) | S: O(n)
def count_bits(n):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)
    return dp

Use the relation: dp[i] = dp[i & (i-1)] + 1.

Diagram

n = 5 dp = [0,0,0,0,0,0] i=1: dp[1] = dp[0] + 1 = 1 i=2: dp[2] = dp[0] + 1 = 1 i=3: dp[3] = dp[2] + 1 = 2 i=4: dp[4] = dp[0] + 1 = 1 i=5: dp[5] = dp[4] + 1 = 2 Result: [0,1,1,2,1,2]
CodeT: O(n) | S: O(n)
def count_bits(n):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i & (i - 1)] + 1
    return dp

Complexity Comparison

For Each Number
T: O(n * 32) = O(n)S: O(n)

Count bits for each number independently.

DP - Least Significant Bit
T: O(n)S: O(n)

Use the relation: dp[i] = dp[i >> 1] + (i & 1).

DP - Brian Kernighan
T: O(n)S: O(n)

Use the relation: dp[i] = dp[i & (i-1)] + 1.

Common Mistakes

Using string conversion for each number (slower)

Not understanding the DP recurrence relation

Using O(n * 32) time when O(n) is possible

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems