397. Integer Replacement

Given a positive integer `n`, you can apply one of the following operations:

1. If `n` is even, replace `n` with `n / 2`.
2. If `n` is odd, replace `n` with either `n + 1` or `n - 1`.

Return the minimum number of operations needed for `n` to become `1`.

Example 1:

```Input: n = 8
Output: 3
Explanation: 8 -> 4 -> 2 -> 1
```

Example 2:

```Input: n = 7
Output: 4
Explanation: 7 -> 8 -> 4 -> 2 -> 1
or 7 -> 6 -> 3 -> 2 -> 1
```

Example 3:

```Input: n = 4
Output: 2
```

Constraints:

• `1 <= n <= 231 - 1`

397. Integer Replacement
``````struct Solution;

impl Solution {
fn integer_replacement(n: i32) -> i32 {
Self::dfs(n as u32) as i32
}
fn dfs(mut n: u32) -> usize {
if n == 1 {
0
} else {
let mut zeros = 0;
while n & 1 == 0 {
n >>= 1;
zeros += 1;
}
if n == 1 {
zeros
} else {
zeros + 1 + Self::dfs(n + 1).min(Self::dfs(n - 1))
}
}
}
}

#[test]
fn test() {
let n = 8;
let res = 3;
assert_eq!(Solution::integer_replacement(n), res);
let n = 7;
let res = 4;
assert_eq!(Solution::integer_replacement(n), res);
let n = 2147483647;
let res = 32;
assert_eq!(Solution::integer_replacement(n), res);
}
``````