# Java DP Solution

• 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;
}
}
``````

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