Watch 10 video solutions for Counting Bits, a easy level problem involving Dynamic Programming, Bit Manipulation. This walkthrough by NeetCode has 159,557 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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's in the binary representation of i.
Example 1:
Input: n = 2 Output: [0,1,1] Explanation: 0 --> 0 1 --> 1 2 --> 10
Example 2:
Input: n = 5 Output: [0,1,1,2,1,2] Explanation: 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101
Constraints:
0 <= n <= 105
Follow up:
O(n log n). Can you do it in linear time O(n) and possibly in a single pass?__builtin_popcount in C++)?Problem Overview: Given an integer n, return an array ans where ans[i] represents the number of 1 bits in the binary representation of i for every number from 0 to n. The challenge is computing all counts efficiently instead of recalculating bits for each number independently.
Approach 1: Naïve Count Bits Approach (O(n log n) time, O(1) extra space)
The straightforward approach processes each integer from 0 to n and counts the set bits in its binary representation. You repeatedly divide the number by two (right shift) and increment a counter whenever the least significant bit is 1. Another variation uses Brian Kernighan’s trick (x = x & (x - 1)) to remove the lowest set bit until the number becomes zero. This approach is simple and demonstrates understanding of bit manipulation, but each number may take up to O(log n) operations to process. Overall complexity becomes O(n log n). It works fine for small inputs but does redundant work because adjacent numbers share overlapping binary patterns.
Approach 2: Dynamic Programming with Bit Relation (O(n) time, O(n) space)
The optimal solution uses a recurrence relationship between numbers. Observe that shifting a number right removes its least significant bit. The count of set bits for i can be derived from a smaller number: dp[i] = dp[i >> 1] + (i & 1). The expression i >> 1 removes the last bit, while (i & 1) checks whether that removed bit was 1. Since dp[i >> 1] has already been computed earlier, you reuse previously calculated results instead of recomputing the entire bit count.
This creates a bottom‑up dynamic programming solution. Start with dp[0] = 0. Iterate from 1 to n, applying the recurrence. Each step performs constant-time bit operations, producing an overall time complexity of O(n) with O(n) space for the result array.
Another equivalent recurrence uses the expression dp[i] = dp[i & (i - 1)] + 1. The operation i & (i - 1) removes the lowest set bit from i. Since that smaller value already has its bit count stored, you simply add one. Both formulas rely on properties of bit manipulation and reuse computed results, which is the core idea behind dynamic programming.
Recommended for interviews: Interviewers expect the dynamic programming solution with O(n) time. Starting with the naïve bit counting approach shows basic understanding of binary operations. Moving to the recurrence relation demonstrates optimization skills and recognition of overlapping subproblems, which is exactly what the question is designed to test.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naïve Count Bits | O(n log n) | O(1) | Good for understanding basic bit counting or when implementing a quick brute-force solution |
| Dynamic Programming with Bit Relation | O(n) | O(n) | Best choice for interviews and large inputs since each number is computed using previously calculated results |