//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(n1);
}
else {
count =1+ Math.min(integerReplacement(n1),
integerReplacement(n+1));
}
}
return count;
}
Extremely simple Java solution


@labs said in Extremely simple Java solution:
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(n1);
}
else {
count =1+ Math.min(integerReplacement(n1),
integerReplacement(n+1));
}
}return count; }
In case where n == Integer.MAX_VALUE, why didn't you add 1. When you are recursively calling integerReplacement(n1), 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_VALUE1. 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 n1. Since we don't have a selection between n1 and n+1 for this particular case, picking n1 doesn't count as an additional step. This is how I interpreted and I may be wrong too.