C++ 84ms solution (beats 100% of cpp submissions)


  • 1
    S

    Powers of two will always have 1 bit only. So check for this case with

    (x != 0) && !(x & (x-1))

    When a number is not a power of two, find the difference with the largest power of two you've encountered so far:

    i - last_power_of_two = diff

    diff is guaranteed to already be in the results array, and the last power of two will always be 1 bit so the result will be

    1 + results[diff].

    See source:

    namespace {
    	bool isPowerOfTwo(int i){
    
    		return (i != 0 && !(i & (i - 1)));
    	}
    }
    
    vector<int> countBits(int num){
    	if (num < 0)
    		return vector<int>();
    
    	vector<int> results(num + 1);
    
    	int last_power_of_two = 0;
    	for (int i = 0; i <= num; ++i){
    		if (i == 0){
    			results[i] = 0;
    			continue;
    		}
    
    		if (isPowerOfTwo(i)){
    			last_power_of_two = i;
    			results[i] = 1;
    			continue;
    		}
    
    		int diff = i - last_power_of_two;
    		int num_of_bits = results[diff] + 1;
    		results[i] = num_of_bits;
    	}
    
    	return results;
    }

Log in to reply
 

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