```
public class Solution {
public int integerReplacement(int n) {
if(n==1) return 0;
return replace((long)n);
}
public int replace(long n){
if(n==1) return 0;
if(n%2==0){
return 1+replace(n/2);
}
return Math.min(replace(n-1),replace(n+1))+1;
}
}
```