This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

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]`

.

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

**Credits:**

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

b'

\n## Summary

\n## Solutions

\n

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

\n

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

\n\n

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

\n

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

\n

'
\n\n

\nThis 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\n

**Intuition**

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

\n**Algorithm**

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.

\nNow 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.

**Complexity Analysis**

- \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

**Intuition**

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

\n**Algorithm**

Suppose we have an integer:

\n\n\n

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

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

\n\n\n

\nThey are different only in the most significant bit.

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

\n\n\n

\n\n\n

\n\n\n

\n\n\n

\nOne 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.

\nSimilarly, we can generate the results for using as blueprints.

\nIn general, we have the following transition function for popcount :

\n\n\n

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

\npublic 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

**Complexity Analysis**

- \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

**Intuition**

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

\n**Algorithm**

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

\nLet look at the relation between and \n

\n\n\n

\n\n\n

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

\nThus, we have the following transition function of pop count :

\n\n\n

\n\n**Complexity Analysis**

- \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

**Algorithm**

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

\nLast 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**Complexity Analysis**

- \n
- \n
Time complexity : . Same as approach #3.

\n \n - \n
Space complexity : . Same as approach #3.

\n \n