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

  • 5
    class Solution {
        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
                    start_range = i; //save the last multiple of two that you came across
                    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.