# Is this solution O(N) Time ?

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

• Yes, it is.

In fact, the code generates a binary tree just like a heap with exactly `n` internal nodes, and exactly `n + 1` leaves, where an internal node corresponds to a triggering of the statement `res[num]=bits`, and a leaf is corresponding to a triggering of the if-statement. 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 than `n`.

``````         1
/ \
/   \
/     \
2       3
/   \    / \
4     5  X   X
/ \   / \
X   X X   X``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.