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:
Credits:
Special thanks to @ syedee for adding this problem and creating all test cases.
This article is for intermediate readers. It relates to the following ideas: Pop Count, Most Significant Bit, Least Significant Bit, Last Set Bit and Dynamic Programming.
Intuition
Solve the problem for one number and applies that for all.
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.
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.
Complexity Analysis
Time complexity : . For each integer , we need operations where is the number of bits in .
Space complexity : . We need space to store the count results. If we exclude that, it costs only constant space.
Intuition
Use previous count results to generate the count for a new integer.
Algorithm
Suppose we have an integer:
and we already calculated and stored all the results of to .
Then we know that is differ by one bit with a number we already calculated:
They are different only in the most significant bit.
Let's exam the range in the binary form:
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.
Similarly, we can generate the results for using as blueprints.
In general, we have the following transition function for popcount :
With this transition function, we can then apply Dynamic Programming to generate all the pop counts starting from .
public class Solution {
public int[] countBits(int num) {
int[] ans = new int[num + 1];
int i = 0, b = 1;
// [0, b) is calculated
while (b <= num) {
// generate [b, 2b) or [b, num) from [0, b)
while(i < b && i + b <= num){
ans[i + b] = ans[i] + 1;
++i;
}
i = 0; // reset i
b <<= 1; // b = 2b
}
return ans;
}
}
Complexity Analysis
Time complexity : . For each integer we need constant operations which do not depend on the number of bits in .
Space complexity : . We need space to store the count results. If we exclude that, it costs only constant space.
Intuition
We can have different transition functions, as long as is smaller than and their pop counts have a function.
Algorithm
Following the same principle of the previous approach, we can also have a transition function by playing with the least significant bit.
Let look at the relation between and
We can see that is differ than by one bit, because can be considered as the result of removing the least significant bit of .
Thus, we have the following transition function of pop count :
Complexity Analysis
Time complexity : . For each integer we need constant operations which do not depend on the number of bits in .
Space complexity : . Same as approach #2.
Algorithm
With the same logic as previous approaches, we can also manipulate the last set bit.
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:
Complexity Analysis
Time complexity : . Same as approach #3.
Space complexity : . Same as approach #3.