My simple O(1) extra space and O(n) complexity solution that beats 99% C++ submissions


  • 5
    P
    class Solution {
    public:
        vector<int> countBits(int num) {
            vector<int> result{0};
            int start_range= 0 ;
            
            for (int i= 1 ; i <= num; i++)
            {
                if ( (i&(i-1)) == 0)   //checks if the number i is a power of 2
                {
                    result.push_back(1);
                    start_range = i; //save the last multiple of two that you came across
                }
                else
                {
                    result.push_back(1 + result[i-start_range]); //you already have the value for [i-start_range] in your vector. New value is plus one of that 
                }
            }
           return result;   
        }
    };
    

Log in to reply
 

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