Java DP Solution


  • 0
    B

    This solution runs for 4ms in the OJ.

    Consider the number n as an array of bits b[]. My idea is that we start from the highest bit b[k], which is always 1 (here k = floor(log(n) / log(2))), to the lowest bit b[0]. For every bit b[i], we consider the minimal steps we can achieve to reduce the bits b[k] ... b[i] to 1. But this is not enough, because while processing the bits lower than i, there can be 1 carried from the add one operations.

    So to include the carry condition, we define a function d(i, j), i = 0...k, j =0,1, which means for the locations i and the carry j, the minimal steps we need to reduce the higher bits to 1. This is all the information we need to make a decision at position i given b[i]. So it satisify the condition of optimal substructures. We can design our dynamic programming algorithm thereon.

    Next, we think about the state transition process. If b[i] == 1 and j = 0, which means we suppose there is no carry produced from lower bits, we have two options: add 1 to this bit and produce a carry, or minus 1 to this bit and produce no carry. For the first option, the step we will take is d(i+1, 1) + 2. The number 2 comes from the two steps where we add 1 to this bit and remove the resulting 0 in the second step. For the second option, the number will be d(i+1, 0) + 2, similarly. So the new function value should be d(i, 0) = min(d(i+1, 0), d(i+1,1)) + 2. Using this logic, we can derive all the transition equations as follows.

    if (b[i] == 1){                                                                
        d[i][0] = Math.min(d[i + 1][0], d[i + 1][1]) + 2;
        d[i][1] = d[i+1][1] + 1;
    }else{ //b[i] == 0
        d[i][0] = d[i+1][0] + 1;
        d[i][1] = Math.min(d[i + 1][0], d[i + 1][1]) + 2
    }
    

    Since we are only using d values from the i+1 step, we don't need a 2D array to store all the d values; Instead, we use two variables carry and notCarry, for d[i+1][1] and d[i+1][0], respectively. Additionally, we use the third variable prevNotCarry to avoid overriding the previous d values during updates. This leads to the following JAVA program.

    public class Solution {
        public int integerReplacement(int n) {
            int log = 0;
            for (int t = n; t > 0; t = t>>1) log++;
            
            int carry = 1;
            int notCarry = 0;
            int prevNotCarry = 0;
            
            for (int i = log - 2; i >= 0; --i){
                int c = n & (1 << i);
                
                if (c > 0){
                    notCarry = Math.min(prevNotCarry, carry) + 2;
                    carry = 1 + carry;
                    prevNotCarry = notCarry;
                }else{
                    notCarry = prevNotCarry + 1;
                    carry = Math.min(prevNotCarry, carry) + 2;
                    prevNotCarry = notCarry;
                }
            }
            return notCarry;
        }
    }
    

Log in to reply
 

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