Is this solution O(N) Time ?


  • 2
    A
    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;
        }
    };

  • 2
    L

    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

Log in to reply
 

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