Counting Bits LeetCode Solution: DP + Bit Manipulation

Counting Bits (#338) is one of those rare LeetCode problems where the optimal solution fits in a single line of code. The problem asks you to return an array where each index i contains the number of 1-bits in the binary representation of i, for every number from 0 to n. The brute-force approach counts bits individually for each number, but the counting bits leetcode solution uses dynamic programming with bit manipulation to achieve O(n) time.

The key recurrence is dp[i] = dp[i >> 1] + (i & 1). Right-shifting i by one position gives you a smaller number whose bit count you have already computed. The (i & 1) term adds 1 if the last bit was set. This single line builds the entire answer array without ever calling a popcount function.

In this walkthrough, you will understand why this recurrence works, explore an alternative DP formula, and see the solution build step by step for a concrete example.

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1-bits in the binary representation of i. The constraint is clear: you must solve this in O(n) time overall, meaning you cannot afford O(log i) work per number.

For example, if n = 5, the expected output is [0, 1, 1, 2, 1, 2]. The binary representations are 0=000, 1=001, 2=010, 3=011, 4=100, 5=101, and counting the set bits in each gives exactly that array. The naive approach of calling Integer.bitCount or manually counting bits for each number runs in O(n log n) total time, which violates the constraint.

The O(n) requirement is the hint that you need to build each answer from previously computed answers — classic dynamic programming. The question is which subproblem to reuse, and that is where bit manipulation enters the picture.

The recurrence dp[i] = dp[i >> 1] + (i & 1) is the heart of the counting bits dp solution. Here is why it works. Consider any number i in binary. Right-shifting by one (i >> 1) removes the last bit, giving you the number formed by all bits except the least significant one. You have already computed the bit count for that smaller number.

The term (i & 1) checks whether the last bit of i is 1 or 0. If it is 1, you need to add one more to the count. If it is 0, the count is the same as i >> 1. Together, these two operations decompose the bit count of any number into a previously solved subproblem plus a constant-time check.

The implementation is minimal. Initialize an array of size n + 1 with ans[0] = 0. Then loop from 1 to n, setting ans[i] = ans[i >> 1] + (i & 1). Each step is O(1), and you do n steps, giving O(n) total time and O(n) space for the output array (which you have to return anyway).

There is a second DP formula that works equally well: dp[i] = dp[i & (i-1)] + 1. The expression i & (i-1) clears the lowest set bit of i. For example, 6 (110) & 5 (101) = 4 (100) — the lowest set bit of 6 was removed. Since you cleared exactly one set bit, the bit count of i is one more than the bit count of i & (i-1).

This formula is popular because i & (i-1) is a classic bit manipulation trick that appears in other problems like Power of Two (#231) and Number of 1 Bits (#191). If you already know this trick, the recurrence is immediately intuitive. The base case is dp[0] = 0, and for every i >= 1, i & (i-1) is strictly less than i, so the subproblem is always already computed.

Both approaches produce identical results with the same O(n) time and O(n) space complexity. The right-shift version is arguably more intuitive because it mirrors how binary numbers work positionally. The clear-lowest-bit version connects to a wider family of bit tricks. Choose whichever clicks for you in an interview setting.

Let us trace dp[i] = dp[i >> 1] + (i & 1) step by step for n = 5. Start with dp[0] = 0 since zero has no set bits.

For i = 1: binary is 1. i >> 1 = 0, (i & 1) = 1. dp[1] = dp[0] + 1 = 0 + 1 = 1. For i = 2: binary is 10. i >> 1 = 1, (i & 1) = 0. dp[2] = dp[1] + 0 = 1 + 0 = 1. For i = 3: binary is 11. i >> 1 = 1, (i & 1) = 1. dp[3] = dp[1] + 1 = 1 + 1 = 2.

For i = 4: binary is 100. i >> 1 = 2, (i & 1) = 0. dp[4] = dp[2] + 0 = 1 + 0 = 1. For i = 5: binary is 101. i >> 1 = 2, (i & 1) = 1. dp[5] = dp[2] + 1 = 1 + 1 = 2. The final array is [0, 1, 1, 2, 1, 2], which matches the expected output.

Notice how each computation references only previously computed values and requires exactly one right-shift and one bitwise AND. No loops within loops, no popcount calls — just a clean O(1) operation per index building on the DP table.

The simplest edge case is n = 0. The output is just [0] — zero has no set bits. Your loop from 1 to n does not execute, and you return the initialized array with a single zero. This is worth testing to make sure your loop bounds are correct.

For n = 1, the output is [0, 1]. This confirms the base case and the first recurrence step. For n = 2, you get [0, 1, 1], showing that 2 (binary 10) has only one set bit despite being larger than 1.

Powers of two are interesting because they always have exactly one set bit. So dp[1] = dp[2] = dp[4] = dp[8] = 1. Numbers of the form 2^k - 1 (like 3, 7, 15, 31) have all bits set, so dp[2^k - 1] = k. These patterns can serve as quick sanity checks during an interview.

Counting Bits (#338) is a masterclass in combining two fundamental techniques. The dynamic programming aspect teaches you to identify subproblems that overlap — every number's bit count depends on a smaller number's bit count. The bit manipulation aspect gives you the specific decomposition: right-shift or clear-lowest-bit.

This problem is closely related to Number of 1 Bits (#191), which counts set bits for a single number using the n & (n-1) trick. Counting Bits extends that idea across an entire array by recognizing that the single-number trick creates a dependency chain you can exploit with DP. Once you see this connection, the hamming weight array builds itself.

Practice this pattern alongside other bit manipulation problems like Single Number (#136), Power of Two (#231), and Missing Number (#268). Together, they build an intuition for when bit operations can replace arithmetic or iteration. Review with YeetCode flashcards to make the dp[i] = dp[i >> 1] + (i & 1) recurrence automatic recall.