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.
This approach involves converting each number to its binary representation and counting the number of 1's in this binary form. We'll iterate through each number from 0 to n, convert the number to its binary form using standard built-in methods, and then count the number of 1's using another built-in method or implement a small function for counting.
The function countBits allocates memory for the result array and initializes a loop to iterate over each number from 0 to n. Inside the loop, another while loop is used to count the number of 1's in the binary representation of the current number using bitwise AND and right shift operations.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to the division operations in each loop.
Space Complexity: O(n) for the result array.
This optimized approach utilizes dynamic programming. The key observation is that for a number i, the number of 1's is equal to the number of 1's in i/2 plus i mod 2. This allows us to build the array progressively and with linear time complexity.
The function initializes the result array with the base case of zero bits for zero. For each i from 1 to n, it calculates the number of 1's as the sum of bits in i/2 and the last bit of i using bitwise operations.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) due to a single loop.
Space Complexity: O(n) for the output array.
| Approach | Complexity |
|---|---|
| Naïve Count Bits Approach | Time Complexity: O(n log n) due to the division operations in each loop. |
| Dynamic Programming Approach | Time Complexity: O(n) due to a single loop. |
| 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 |
Counting Bits - Dynamic Programming - Leetcode 338 - Python • NeetCode • 159,557 views views
Watch 9 more video solutions →Practice Counting Bits with our built-in code editor and test cases.
Practice on FleetCode