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.
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; }}Video 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.