# JAVA 4ms Solution with Detail Explanation

• General idea is how to eliminate all bits from the right.

If `n%2 == 0`, we can use `n/2`, since it eliminate `1` bit per operation, eg. `10->1`.

If `n%2 == 1`, first choice is using `n-1` and `n/2`, and we use `2` operations to eliminate `1` bit, eg1. `11->10->1`, eg.2 `x011->x010->x01->x00->x0`.
Another choice is use `n+1` and several `n/2` to deal with continuous bits `1`, but this may not be always better than the above one. eg.1 `11->100->10->1`, eg.2`x011->x100->x10->x1->(x0)`. Note `x1` may form another continuous `1` sequence with potential last bits of `1` in `x`, and it always no worse than first choice in this situation.

The truth is for longer continuous `1`, second choice is better, and the division is that we have `3+` `1`s, or we have some sequence and `011` at the last.

Here is the codes:

``````public class Solution {
public int integerReplacement(int n) {
int step = 0, count = 0;
while(n>0){
if((n&1)==0) {
step +=1;
n = n>>1;
}
else{
while((n&1)!=0){
count += 1;
n = n>>1;
}
if(count>2||n!=0&&count==2) {
step+=count+1;
n = (n|1);
}
else step += count<<1;
count = 0;
}
}
return step-2;
}
}
``````

Note, since we tried to eliminate all bits, and in fact we do not need the last `2` steps, `1->0->`, so we return `step-2`.

The complexity should be `olog(n)`.

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