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

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;
    }
};