Counting Bits
EasyPrompt
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 --> 10Example 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++)?
Approaches
3 approaches with complexity analysis and trade-offs.
This is a straightforward brute-force approach. We iterate through each number from 0 to n. For each number, we manually count the number of set bits (1s) in its binary representation by repeatedly checking the last bit and shifting.
Algorithm
- Initialize an array
ansof sizen + 1. - Loop
ifrom0ton:- Initialize
count = 0andnum = i. - While
num > 0:- Add the last bit to the count:
count += num & 1. - Right shift the number to process the next bit:
num >>= 1.
- Add the last bit to the count:
- Store the result:
ans[i] = count.
- Initialize
- Return
ans.
Walkthrough
The algorithm iterates through each integer from 0 to n. For each integer i, it calculates the number of set bits. This is done using a nested loop where we check the least significant bit (LSB) of the current number. If the LSB is 1, we increment a counter. Then, we perform a right bit shift on the number to discard the LSB and check the next bit. This process is repeated until the number becomes 0. The final count for i is stored in ans[i].
public int[] countBits(int n) { int[] ans = new int[n + 1]; for (int i = 0; i <= n; i++) { int count = 0; int num = i; while (num > 0) { count += num & 1; num >>= 1; } ans[i] = count; } return ans;}Complexity
Time
O(n log n) - The outer loop runs `n + 1` times. For each number `i`, the inner while loop runs `log(i)` times (the number of bits in `i`). Therefore, the total time complexity is the sum of `log(i)` for `i` from 1 to `n`.
Space
O(n) - The space required is for the output array `ans` of size `n + 1`. If the output array is not considered, the space complexity is O(1).
Trade-offs
Pros
Simple to understand and implement.
Does not require any complex mathematical insights.
Cons
Inefficient compared to linear time solutions.
It recomputes the bit count for each number from scratch, ignoring relationships between numbers.
This approach uses dynamic programming to achieve a linear time solution. It finds a recurrence relation between the bit count of a number i and the bit count of a smaller, related number. By observing the relationship between i and i / 2 (or i >> 1), we can compute the result in a single pass.
Algorithm
- Initialize an array
ansof sizen + 1. - The base case
ans[0]is0. - Loop
ifrom1ton:- Apply the recurrence relation:
ans[i] = ans[i >> 1] + (i & 1).
- Apply the recurrence relation:
- Return
ans.
Walkthrough
The core idea is that the number of set bits in i is closely related to the number of set bits in i >> 1 (i.e., i shifted right by one bit).
- If
iis an even number, its binary representation is the same asi/2with a0appended. Thus, they have the same number of set bits.countBits(i) = countBits(i/2). - If
iis an odd number, its binary representation is the same asi/2with a1appended. Thus, it has one more set bit thani/2.countBits(i) = countBits(i/2) + 1.
These two cases can be combined into a single, elegant formula: countBits(i) = countBits(i >> 1) + (i & 1). The term (i & 1) evaluates to 0 for even i and 1 for odd i. We can build our ans array iteratively using this recurrence, as ans[i >> 1] will always have been computed before we calculate ans[i].
public int[] countBits(int n) { int[] ans = new int[n + 1]; for (int i = 1; i <= n; i++) { // ans[i >> 1] is the bit count of i without its last bit. // (i & 1) is the value of the last bit of i. ans[i] = ans[i >> 1] + (i & 1); } return ans;}Complexity
Time
O(n) - We iterate from `1` to `n` in a single pass, and each step involves constant time bitwise operations.
Space
O(n) - To store the result array `ans` of size `n + 1`.
Trade-offs
Pros
Highly efficient with O(n) time complexity.
Solves the problem in a single pass, satisfying the follow-up.
The solution is elegant and concise.
Cons
Requires O(n) space for the DP table, although this is used for the output array.
This is another highly efficient dynamic programming approach that leverages a clever bit manipulation trick. The core idea is that for any number x, the expression x & (x - 1) clears the rightmost set bit. This property allows us to establish a different recurrence relation.
Algorithm
- Initialize an array
ansof sizen + 1. - The base case
ans[0]is0. - Loop
ifrom1ton:- Apply the recurrence relation:
ans[i] = ans[i & (i - 1)] + 1.
- Apply the recurrence relation:
- Return
ans.
Walkthrough
The trick, sometimes associated with Brian Kernighan's algorithm, is that i & (i - 1) results in a number that is identical to i but with its rightmost '1' bit flipped to '0'. This means i & (i - 1) has exactly one fewer set bit than i.
This observation gives us the recurrence relation: countBits(i) = countBits(i & (i - 1)) + 1.
Since i & (i - 1) is always smaller than i, we can guarantee that ans[i & (i - 1)] has already been computed when we need to calculate ans[i]. We can build our solution array iteratively from 1 to n using this principle.
public int[] countBits(int n) { int[] ans = new int[n + 1]; for (int i = 1; i <= n; i++) { // i & (i - 1) has one less set bit than i. ans[i] = ans[i & (i - 1)] + 1; } return ans;}Complexity
Time
O(n) - A single loop from `1` to `n` with constant time operations inside.
Space
O(n) - The space is dominated by the output array of size `n + 1`.
Trade-offs
Pros
Achieves optimal O(n) time complexity in a single pass.
Demonstrates a powerful and widely applicable bit manipulation technique.
Very concise and efficient implementation.
Cons
The logic behind
i & (i - 1)might be slightly less intuitive for beginners compared to the LSB approach.
Solutions
Solution
class Solution {public int[] countBits(int n) { int[] ans = new int[n + 1]; for (int i = 1; i <= n; ++i) { ans[i] = ans[i & (i - 1)] + 1; } return ans; }}class Solution {public: vector<int> countBits(int n) { vector<int> ans(n + 1); for (int i = 0; i <= n; ++i) { ans[i] = __builtin_popcount(i); } return ans; }};class Solution: def countBits(self, n: int) -> List[int]: ans = [0] * (n + 1) for i in range(1, n + 1): ans[i] = ans[i & (i - 1)] + 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.