0 to n.
Problem
You are given a non-negative integern. Return an array ans of length n + 1, where ans[i] is the number of 1 bits in the binary representation of i.
The solution should run in
O(n) time.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
n = 5Output
[0, 1, 1, 2, 1, 2]0 = 0000
1 = 0001
2 = 0010
3 = 0011
4 = 0100
5 = 0101[0, 1, 1, 2, 1, 2]Solution
We can solve this problem using Dynamic Programming and bit manipulation.For every number
i, the expression i & (i - 1) removes its rightmost set bit. Therefore, the number of set bits in i is one more than the number of set bits in i & (i - 1).
This gives us the recurrence:
ans[i] = ans[i & (i - 1)] + 1i & (i - 1) is always smaller than i, its answer has already been calculated.
class Solution {
public int[] countBits(int n) {
// Create an array to hold results from 0 to n
int[] bits = new int[n + 1];
// Base case: 0 has 0 set bits (already 0 by default in Java)
for (int i = 1; i <= n; i++) {
// i & (i - 1) clears the lowest set bit.
// We take the bit count of that smaller number and add 1.
bits[i] = bits[i & (i - 1)] + 1;
}
return bits;
}
}
Complexity
Each number from1 to n is processed once, resulting in O(n) time complexity. The output array contains n + 1 elements, resulting in O(n) space complexity.