338. Counting Bits

1. Description

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.

2. Example

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

3. Constraints

• 0 <= n <= 10$^{5}$

4. Solutions

Bit Manipulation && Dynamic Programming

Time complexity: O(n)
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> bit_count(n + 1, 0);
        for (int i = 1; i <= n; ++i) {
            bit_count[i] = bit_count[i & (i - 1)] + 1;
        }

        return bit_count;
    }
};