Same idea with other recursive solutions, but two ticky points here.

- With the helper of hashmap, we don't need to search for one intermediate result multiple times
- To hand the overflow for test case INT.MAX, use
`1 + (n - 1) / 2`

instead of`(n + 1) / 2`

. The idea comes from solving some binary search questions. To avoid overflow, we use`int mid = start + (end - start) / 2`

instead of`int mid = (start + end) / 2`

```
public class Solution {
public int integerReplacement(int n) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
map.put(1, 0);
map.put(2, 1);
return helper(n, map);
}
private int helper(int n, Map<Integer, Integer> map) {
if (map.containsKey(n)) {
return map.get(n);
}
int steps = -1;
if (n % 2 == 0) {
steps = helper(n / 2, map) + 1;
} else {
steps = Math.min(helper((n - 1), map) + 1, helper(1 + (n - 1) / 2, map) + 2);
}
map.put(n, steps);
return steps;
}
}
```