Counting Bits Solution

Problem

Given a non-negative integer n, return an array of length n + 1 where each position i holds the count of 1 bits in the binary representation of i. Think of it as building a lookup table of popcount values for every integer from 0 through n.

Input: n = 5
Output: [0, 1, 1, 2, 1, 2]
Explanation: 5 in binary is 101 (two 1-bits), 4 is 100 (one 1-bit), 3 is 11 (two 1-bits), and so on back to 0

Intuition

The straightforward path counts bits in each number from scratch. The key insight is that every number's bit count is already encoded in a smaller number you've visited: shifting right by one drops the lowest bit, so count(i) = count(i / 2) + (is i odd?). Because we fill the table from index 0 upward, every entry we need is already computed by the time we reach i.

Approach 1 — Brute Force

For each number from 0 to n, count its 1-bits by repeatedly checking the lowest bit and right-shifting until nothing remains.

Initialize an empty result array
For each num from 0 to n:
- Copy num into a temporary variable so the loop variable stays intact
- Count bits: while temp is non-zero, add the lowest bit and shift right
- Append the count to the result
Return result

1def countBits(n: int) -> list[int]:
2    result = []
3    for num in range(n + 1):
4        bit_count = 0
5        remaining = num          # copy so we don't mutate the loop variable
6        while remaining:
7            bit_count += remaining & 1   # 1 if lowest bit is set, else 0
8            remaining >>= 1              # drop the lowest bit
9        result.append(bit_count)
10    return result

Time: O(n log n) — each of the n+1 numbers requires up to log₂(n) shifts to fully process.
Space: O(1) extra — only the output array is used.

Approach 2 — Dynamic Programming

Reuse the bit count already stored for i >> 1: any number's popcount equals the popcount of half that number plus 1 if the number is odd.

Allocate bit_count of size n + 1, all zeros
For each i from 1 to n:
- bit_count[i] = bit_count[i >> 1] + (i & 1)
- i >> 1 is i with its lowest bit dropped (already in the table); i & 1 adds that bit back if it was 1
Return bit_count

1def countBits(n: int) -> list[int]:
2    bit_count = [0] * (n + 1)
3    for i in range(1, n + 1):
4        bit_count[i] = bit_count[i >> 1] + (i & 1)  # half of i is already in the table
5    return bit_count

Time: O(n) — exactly one constant-time operation per index.
Space: O(1) extra — only the output array is used, no auxiliary structures.

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n log n)	O(1) extra	Learning bit operations or n is trivially small
DP (bit shift)	O(n)	O(1) extra	Always — same memory footprint, strictly faster

Common Mistakes

Allocating n elements instead of n+1: the output spans indices 0 through n inclusive — new int[n] is one entry short and causes an out-of-bounds write at the last step.
Left shift instead of right: i << 1 doubles i and jumps past the computed table; the recurrence needs i >> 1 to look up the answer for i / 2.
Mutating the loop variable in brute force: writing while num: num >>= 1 overwrites the index — always copy into a temporary like remaining = num before the inner loop.
Wrong bit selector: i & 1 checks whether the lowest bit is set (i.e., whether i is odd); using i & 2 instead checks the second bit, producing wrong counts for every odd number.
Misplacing dp[0]: the base case bit_count[0] = 0 is automatically correct in every language's default initialization — manually setting it to 1 breaks every even number built on top of it.

Counting Bits — Solution