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 1:
Input: 2
Output: [0,1,1]
Example 2:
Input: 5
Output: [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.
Approach #1: Math. [C++]
class Solution {
public:
vector<int> countBits(int num) {
vector<int> temp(num+1, 0);
for (int i = 1; i <= num; ++i) {
temp[i] = temp[i&(i-1)] + 1;
}
return temp;
}
};
Analysis:
i binary count i&(i-1)
0 0 0
1 0001 1 0000 -> 0
2 0010 1 0000 0
3 0011 2 0010 2
4 0100 1 0000 0
5 0101 2 0100 4
6 0110 2 0100 4
7 0111 3 0110 6
8 1000 1 0000 0
We can find some regular about:
the count of '1' in the i(binary) = the count of '1' in the i&(i-1)(binary) + 1;
temp[i] = temp[i&(i-1)] + 1;
Approach #2: bitset. [C++]
class Solution {
public:
vector<int> countBits(int num) {
vector<int> res;
for (int i = 0; i <= num; ++i) {
res.push_back(bitset<32>(i).count());
}
return res;
}
};
Analysis:
There is a trick of the function bitset. Using this function we can directly calculate the number of '1' in the i's binary form.
Reference:
http://www.cplusplus.com/reference/bitset/bitset/count/
http://www.cnblogs.com/grandyang/p/5294255.html