Highly intuitive Java solution using DP


  • 0
    V
    This solution uses DP as previous calculated values of array elements are used to calculate next values.
    Basically there are two cases which can be intuitively figured out once sequence of few numbers is written in their bit representation. 
    Eg:
    0 -> 000
    1 -> 001
    2 -> 010
    3 -> 011
    4 -> 100
    5 -> 101
    6 -> 110
    7 -> 111
    
    We can deduce from above example that there are only two cases two handle, which are:
    1) If number is power of 2, it can be represented by only single 1.(numbers 1, 2, 4 in the example).
    2) Other numbers can be found by adding 1 to value stored in result[i - lastPowerOfTwo], where i is the current element.
    This case is highly intuitive as i can be formed by adding lastPowerOfTwo (having single 1 in binary representation) to the remaining value: i - lastPowerOfTwo. 
    In the example result[5] can be formed by adding 1 + resu1t[5 - 4]. Therefore, result[5] = 2
    
    
    public int[] countBits(int num) {
    	int result[] = new int[num + 1];
    	int lastPowerOfTwo = 0;
    	int curPowerValue = 0;
    	for (int i = 1; i <= num; i++) {
    		// check if current number is power of 2
    		if (Math.pow(2, curPowerValue) == i) {
    			result[i] = 1;
    			lastPowerOfTwo = i;
    			curPowerValue++;
    		} else {
    			result[i] = 1 + result[i - lastPowerOfTwo];
    		}
    	}
    	return result;
    }

Log in to reply
 

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