Just do it recursively, be careful with integer overflow.

For a odd number we only have two choices -1 or +1, my idea is to reduce the problem size.

```
int min(int a, int b){
return a < b ? a:b;
}
int func(int n){
if(n == 1) return 0;
if(n % 2 ){
return min(func(n-1)+1 , func((n-1)/2 + 1) + 2);
} else{
return func(n/2) + 1;
}
}
int integerReplacement(int n) {
return func(n);
}
```