class Solution {

public:

vector<int> countBits(int num) {

vector<int> v(num + 2, 0);

int p = 2, p1;

v[0] = 0;

v[1] = 1;

for(int i = 2; i <= num; i += 2) {

if (i == p) {

v[i] = 1;

v[i+1] = 2;

p1 = p;

p <<= 1;

continue;

}

int q = i % p1;

v[i] = v[q] + 1;

v[i + 1] = v[q] + 2;

}

v.pop_back();

return v;

};