## 338. Counting Bits

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:
For num = 5 you should return [0,1,1,2,1,2].

• 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.

Credits:
Special thanks to @ syedee for adding this problem and creating all test cases.

b'
\n\n

## Summary

\n

This article is for intermediate readers. It relates to the following ideas:\nPop Count, Most Significant Bit, Least Significant Bit, Last Set Bit and Dynamic Programming.

\n

## Solutions

\n
\n

#### Approach #1 Pop Count [Accepted]

\n

Intuition

\n

Solve the problem for one number and applies that for all.

\n

Algorithm

\n

This problem can be seen as a follow-up of the Problem 191 The number of 1 bits. It counts the bits for an unsigned integer. The number is often called pop count or Hamming weight. See the editorial of Problem 191 The number of 1 bits for a detailed explanation of different approaches.

\n

Now we just take that for granted. And suppose we have the function int popcount(int x) which will return the count of the bits for a given non-negative integer. We just loop through the numbers in range [0, num] and put the results in a list.

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . For each integer , we need operations where is the number of bits in .

\n
• \n
• \n

Space complexity : . We need space to store the count results. If we exclude that, it costs only constant space.

\n
• \n
\n
\n

#### Approach #2 DP + Most Significant Bit [Accepted]

\n

Intuition

\n

Use previous count results to generate the count for a new integer.

\n

Algorithm

\n

Suppose we have an integer:

\n

\n\n

\n

and we already calculated and stored all the results of to .

\n

Then we know that is differ by one bit with a number we already calculated:

\n

\n\n

\n

They are different only in the most significant bit.

\n

Let\'s exam the range in the binary form:

\n

\n\n

\n

\n\n

\n

\n\n

\n

\n\n

\n

One can see that the binary form of 2 and 3 can be generated by adding 1 bit in front of 0 and 1. Thus, they are different only by 1 regarding pop count.

\n

Similarly, we can generate the results for using as blueprints.

\n

In general, we have the following transition function for popcount :

\n

\n\n

\n

With this transition function, we can then apply Dynamic Programming to generate all the pop counts starting from .

\n
public class Solution {\n    public int[] countBits(int num) {\n        int[] ans = new int[num + 1];\n        int i = 0, b = 1;\n        // [0, b) is calculated\n        while (b <= num) {\n            // generate [b, 2b) or [b, num) from [0, b)\n            while(i < b && i + b <= num){\n                ans[i + b] = ans[i] + 1;\n                ++i;\n            }\n            i = 0;   // reset i\n            b <<= 1; // b = 2b\n        }\n        return ans;\n    }\n}\n
\n

Complexity Analysis

\n
\n
• \n

Time complexity : . For each integer we need constant operations which do not depend on the number of bits in .

\n
• \n
• \n

Space complexity : . We need space to store the count results. If we exclude that, it costs only constant space.

\n
• \n
\n
\n

#### Approach #3 DP + Least Significant Bit [Accepted]

\n

Intuition

\n

We can have different transition functions, as long as is smaller than and their pop counts have a function.

\n

Algorithm

\n

Following the same principle of the previous approach, we can also have a transition function by playing with the least significant bit.

\n

Let look at the relation between and \n

\n

\n\n

\n

\n\n

\n

We can see that is differ than by one bit, because can be considered as the result of removing the least significant bit of .

\n

Thus, we have the following transition function of pop count :

\n

\n\n

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . For each integer we need constant operations which do not depend on the number of bits in .

\n
• \n
• \n

Space complexity : . Same as approach #2.

\n
• \n
\n
\n

#### Approach #4 DP + Last Set Bit [Accepted]

\n

Algorithm

\n

With the same logic as previous approaches, we can also manipulate the last set bit.

\n

Last set bit is the rightmost set bit. Setting that bit to zero with the bit trick, x &= x - 1, leads to the following transition function:

\n

\n\n

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . Same as approach #3.

\n
• \n
• \n

Space complexity : . Same as approach #3.

\n
• \n
\n
'