Reference: LeetCode
Difficulty: Medium

## Problem

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.

Example:

• It is very easy to come up with a solution with runtime $O(n \times \text{sizeof}(\text{int}))$. 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.

## Analysis

Methods:

1. Brute-Force
• For each value, count the number of bits.

Time: $O(NM)$. $M$ is the number of bits.
Space: $O(N)$

1. DP + Least Significant Bit
• We can observe that for a digit abcd in binary form, a transition function could be:
• dp[abcd] = dp[abc] + dp[d] = dp[abc >>> 1] + (d & 1).

Time: $O(N)$
Space: $O(N)$

1. DP + Most Significant Bit
• I think this one is less elegant.

Time: $O(N \times \text{sizeof}(int))$
Space: $O(N)$

1. DP + Last Set Bit
• With the same logic as previous approaches, we can also do it with the last set bit. For x, we have:
• dp[x] = dp[x & (x - 1)] + 1
• Note: loop should start from 1 since dp = dp[0 & -1] + 1 = 1.

Time: $O(N)$
Space: $O(N)$

Comment Junhao Wang
Hi, I was a master student at USC studying Computer Science.