Idea is pretty straightforward: recursively halve n until it becomes 1. Odd number needs to be handled carefully to avoid overflow.

```
public int integerReplacement(int n) {
if (n == 1) {
return 0;
}
if (n % 2 == 0) {
return integerReplacement(n / 2) + 1;
} else {
return Math.min(integerReplacement(n / 2 + 1), integerReplacement(n / 2)) + 2;
}
}
```