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 --> 10
Example 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
My Solution
We can solve this problem by counting the number of set bits in every number from 0 to n. We do this by AND-ing every number by 1 and right shifting the number by 1 to move onto the next bit.
Since we are dealing with 32 bit integers, we right shift a maximum of 32 times for each number from 0 to n. This is a constant number so time complexity would be O(n). Space complexity would also be O(n) to store the output.
class Solution {
public int[] countBits(int n) {
int[] out = new int[n+1];
for (int i = 0; i <= n; i++) {
int num = i;
while (num > 0) {
out[i] += (num & 1);
num >>= 1;
}
}
return out;
}
}