Counting Bits - Solution & Explanation
Problem Statement
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:
- It is very easy to come up with a solution with a runtime of
O(n log n). Can you do it in linear timeO(n)and possibly in a single pass? - Can you do it without using any built-in function (i.e., like
__builtin_popcountin C++)?
Approach Overview
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 1: Naïve Count Bits Approach
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.
Complexity
Time Complexity: O(n log n) due to the division operations in each loop.
Space Complexity: O(n) for the result array.
Approach 2: Dynamic Programming Approach
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.
Complexity
Time Complexity: O(n) due to a single loop.
Space Complexity: O(n) for the output array.
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| 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. |
| Default Approach | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Counting Bits - Dynamic Programming - Leetcode 338 - Python • NeetCode • 206,527 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Counting Bits easy or hard?
How to solve Counting Bits in O(n)?
What is the best approach for Counting Bits?
What data structure is used in Counting Bits?
What is the time complexity of Counting Bits?
Counting Bits Python or Java solution approach?
Is Counting Bits asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Counting Bits with our built-in code editor and test cases.
Practice on FleetCode