Back to Bit Manipulation
Easy
Counting Bits
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`.
Examples
Input:n = 2
Output:[0,1,1]
0 --> 0
1 --> 1
2 --> 10
Input:n = 5
Output:[0,1,1,2,1,2]
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
Constraints
0 <= n <= 10^5
Dynamic Programming + Bit Manipulation
Approach
We can compute the number of 1-bits for each number from 0 to `n` in O(1) time per number by using previously computed results. The number of 1-bits in `i` is equal to the number of 1-bits in `i / 2` (which is `i >> 1`) plus 1 if `i` is odd (`i % 2 == 1`). So, `ans[i] = ans[i >> 1] + (i & 1)`. We can build the `ans` array iteratively.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
Time complexity is O(n) as we compute each value in O(1) time. Space complexity is O(n) for the output array (or O(1) auxiliary space).
Solution.java
class Solution { public int[] countBits(int n) { int[] dp = new int[n + 1]; dp[0] = 0; for (int i = 1; i <= n; i++) { // i >> 1 is the same as i / 2 // i & 1 is the same as i % 2 dp[i] = dp[i >> 1] + (i & 1); } return dp; }}