Counting Bits
Problem
Given an integer n, return an array ans of length n + 1 where ans[i] is the number of 1s in the binary representation of i, for every i from 0 to n.
Examples
Example 1
Input: n = 2
Output: [0,1,1]
Explanation: 0 -> 0, 1 -> 1, 2 (binary 10) -> 1
Example 2
Input: n = 5
Output: [0,1,1,2,1,2]
Explanation: 5 = 101 in binary -> 2 set bits
Constraints
- •
0 <= n <= 10^5
Hints
Hint 1
The brute force counts each number's bits independently (e.g. via Brian Kernighan's n &= (n-1) trick, repeated until n is 0) — correct, but redundant work across nearby numbers.
Hint 2
Can the answer for i be built from the answer for some SMALLER number you've already computed, instead of counting from scratch?
Hint 3
i >> 1 drops i's lowest bit — ans[i >> 1] already has the count for everything else; add back 1 if that dropped bit was itself a 1 (i.e. i is odd).
Solutions
public int[] countBitsBruteForce(int n) {
int[] ans = new int[n + 1];
for (int i = 0; i <= n; i++) {
int num = i, count = 0;
while (num != 0) {
num &= (num - 1); // clears the lowest set bit
count++;
}
ans[i] = count;
}
return ans;
}Time: O(n log(max n)) · Space: O(n) for output, O(1) extra