# Extremely simple Java solution

• ``````//4 : 1+1+integerReplacement(1)
public int integerReplacement(int n) {
if(n<=1) {
return 0;
}
int count=Integer.MAX_VALUE;
if(n%2==0) {
count = 1 + integerReplacement(n/2);
}
else {
if(n==Integer.MAX_VALUE) {
count = integerReplacement(n-1);
}
else {
count =1+ Math.min(integerReplacement(n-1),
integerReplacement(n+1));
}
}

return count;
}
``````

• public int integerReplacement(int n) {
if(n<=1) {
return 0;
}
int count=Integer.MAX_VALUE;
if(n%2==0) {
count = 1 + integerReplacement(n/2);
}
else {
if(n==Integer.MAX_VALUE) {
count = integerReplacement(n-1);
}
else {
count =1+ Math.min(integerReplacement(n-1),
integerReplacement(n+1));
}
}

``````    return count;
}
``````

In case where n == Integer.MAX_VALUE, why didn't you add 1. When you are recursively calling integerReplacement(n-1), you have taken one step by subtracting 1. So, in my opinion, 1 should be added. Correct me if I am wrong.

• @satvirgrewal Hi..the constraint is :

``````If n is even, replace n with n/2.
If n is odd, you can replace n with either n + 1 or n - 1.
``````

The max_value is an odd number so the idea is to get an even number below it. If you add 1 to it, it will overflow. Let me know if you have any further questions on this solution.

• @labs Thanks for the prompt response.
I agree with the constraint explanation. When we have the max value, we definitely should not add 1 as it will cause overflow. So we are left with subtracting one. Fine till this point.
But when we have the input as the MAX_VALUE, we subtract 1 out of it and calls the method again. So the call will get us the steps taken for MAX_VALUE-1. But in the above solution, we are not counting the very first step taken, i.e. subtracting 1 from MAX_INTEGER.
With the above solution,
2147483647 and 2147483646 will take the same number of steps in reaching to 1. I think 2147483647 will need one more step compared to 2147483646.

• @satvirgrewal Very good point! I remember having it like 1+the count as you mentioned. After getting it wrong, my understanding was -- a count of 1 means either n/2 or figuring out n+1 or n-1. Since we don't have a selection between n-1 and n+1 for this particular case, picking n-1 doesn't count as an additional step. This is how I interpreted and I may be wrong too.

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