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].
Idea: Find the pattern in this sequence
class Solution {
public:
vector<int> countBits(int num) {
vector<int> r = vector<int>();
r.reserve(num+1);
r.push_back(0); // non negative int
if(num == 0) return r;
r.push_back(1);
if(num == 1) return r;
for(int p1=1,p2=2;r.size() <= num;p1*=2,p2*=2){
for(int j=p1;j<p2 && r.size() <= num;j++) r.push_back(r[j]);
for(int j=p1;j<p2 && r.size() <= num;j++) r.push_back(r[j] + 1);
}
return r;
}
};
