Counting Bits

Problem

Given an integer n, count the number of 1’s in the binary representation of every number in the range [0, n].

Return an array output where output[i] is the number of 1’s in the binary representation of i.

Examples

Example 1:

Input: n = 4

Output: [0,1,1,2,1]

Explanation:
0 —> 0
1 —> 1
2 —> 10
3 —> 11
4 —> 100

Constraints

• 0 <= n <= 1000

You should aim for a solution with O(n) time and O(n) space, where n is the given integer.

Solution

Multiplying a number by 2 is to shift its bit representation left. Given a number i, we can check how many bits i/2 has (which is the matching part for a shift to the left), then we check if i is odd which accounts for the bit disappearing when we shift to the right.

class Solution {
public:
    vector<int> countBits(int n) {
        std::vector<int> result(n + 1);
        for (int i = 1; i <= n; ++i) {
            result[i] = result[i >> 1] + (i & 1);
        }
        return result;
    }
};