Counting Bits
Given an integer n, return an array of the number of 1 bits in the binary representation of all numbers in the range [0, n].
Constraints:
- 0 <= n <= 10^5
- The input will be a single integer n.
Examples:
Input: 2
Output: [0,1,1]
Explanation: The binary representation of 0 is 0, 1 is 1, and 2 is 10. Therefore, the number of 1 bits in the binary representation of all numbers in the range [0, 2] is [0, 1, 1].
Input: 5
Output: [0,1,1,2,1,2]
Explanation: The binary representation of 0 is 0, 1 is 1, 2 is 10, 3 is 11, 4 is 100, and 5 is 101. Therefore, the number of 1 bits in the binary representation of all numbers in the range [0, 5] is [0, 1, 1, 2, 1, 2].
Solutions
Dynamic Programming
The idea is to use dynamic programming to store the number of 1 bits in the binary representation of all numbers in the range [0, n]. For each number i, we can calculate the number of 1 bits by shifting the bits of i to the right by 1 and adding the least significant bit of i.
public int[] countBits(int n) {
int[] res = new int[n + 1];
for (int i = 1;
i <= n;
i++) {
res[i] = res[i >> 1] + (i & 1);
}
return res;
}Follow-up:
How would you optimize the solution if n is very large?
