Counting Bits

Counting Bits

What is this problem about?

The Counting Bits interview question asks you to return an array of length $n+1$ where each entry $i$ is the number of 1s in the binary representation of the integer $i$ (from $0$ to $n$). For example, if $n=2$, you need to return counts for 0 (00), 1 (01), and 2 (10), which is [0, 1, 1].

Why is this asked in interviews?

Companies like Uber and Nvidia use this Bit Manipulation interview pattern to see if a candidate can optimize a calculation using previously computed values. While you could calculate bits for each number independently in O(n log n), the goal is to solve it in O(n) using Dynamic Programming. It tests your ability to find mathematical relationships between binary numbers.

Algorithmic pattern used

This problem is solved using Dynamic Programming with Bit Manipulation. There are several relationships you can use:

1. Offset: dp[i] = dp[i - offset] + 1, where offset is the largest power of 2 less than or equal to $i$.
2. LSB (Least Significant Bit): dp[i] = dp[i >> 1] + (i & 1). The LSB approach is the most elegant: the number of bits in $i$ is the number of bits in $i/2$ plus 1 if $i$ is odd.

Example explanation

$n = 5$

• dp[0] = 0
• dp[1]: dp[1 >> 1] + (1 & 1) = dp[0] + 1 = 1.
• dp[2]: dp[2 >> 1] + (2 & 1) = dp[1] + 0 = 1.
• dp[3]: dp[3 >> 1] + (3 & 1) = dp[1] + 1 = 2.
• dp[4]: dp[4 >> 1] + (4 & 1) = dp[2] + 0 = 1.
• dp[5]: dp[5 >> 1] + (5 & 1) = dp[2] + 1 = 2. Result: [0, 1, 1, 2, 1, 2].

Common mistakes candidates make

• Inefficient calculation: Using built-in "bit count" functions for every number, which is O(n * log n).
• Complexity: Over-complicating the DP transition when simpler bitwise relations exist.
• Memory: Not realizing that the dp array itself is the solution and trying to use extra storage.

Interview preparation tip

Master the expression i >> 1 (division by 2) and i & 1 (parity check). These are fundamental tools for almost any binary-related coding problem.