class Solution {
public:
int Max;
vector <int> res;
void gen(int num,int bits)
{
if(num >Max)
return ;
res[num]=bits;
gen(num*2,bits);
gen(num*2+1,bits+1);
}
vector<int> countBits(int num) {
res.resize(num+1);
res[0]=0;
Max=num;
gen(1,1);
return res;
}
};
Is this solution O(N) Time ?

Yes, it is.
In fact, the code generates a binary tree just like a heap with exactly
n
internal nodes, and exactlyn + 1
leaves, where an internal node corresponds to a triggering of the statementres[num]=bits
, and a leaf is corresponding to a triggering of the ifstatement. Therefore, the overall runtime is proportional to the total size of the tree, which is O(n + n + 1) = O(n).For instance, let n = 5. We have 5 internal nodes (numbers) and 6 leaves (X's). We update
res
array in each internal node, and we prune the recursion at each leaf as its value is greater thann
.1 / \ / \ / \ 2 3 / \ / \ 4 5 X X / \ / \ X X X X