338. Counting Bits

1. Description

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

2. Example

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

Example 2:
Input: 5
Output: [0,1,1,2,1,2]

3. Follow Up

• It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
• Space complexity should be O(n).
• Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

4. Solutions

My Accepted Solution(Follow Up)

n = num
Time complexity: O(n)
Space complexity: O(n)

ontBits[i] means the number of ‘1’ bits in the i-th number
dp = ontBits
$$ \begin{aligned} &dp[i] = \begin{cases} 0, & \text{i == 0} \hspace{100cm}\\
dp[i \& (i - 1)] + 1, & \text{i > 0} \\
\end{cases} \end{aligned} $$

// i & (i - 1) could replace the most right bit 1 in i with bit 0

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> ontBits(num + 1);
        for (int i = 1; i <= num; i++) {
            ontBits[i] = ontBits[i & (i - 1)] + 1;
        }

        return ontBits;
    }
};