## Algorithm

Problem Name: 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`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int integerReplacement(int n) {
int k = 0;
while (n != 1) {
if (n & 1) {
if ((n & 3) == 3 && n > 3) {
n += 1;
} else {
n -= 1;
}
} else {
n = (n >> 1) & 0x7fffffff;
}
k ++;
}
return k;
}
``````
Copy The Code &

Input

cmd
n = 8

Output

cmd
3

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const integerReplacement = function(n, memo = {}) {
if (n === 1) return 0;
if (memo[n]) return memo[n];
memo[n] = n % 2 === 0 ? integerReplacement(n/2, memo) + 1 : Math.min(integerReplacement(n+1, memo), integerReplacement(n-1, memo)) + 1;
return memo[n];
};
``````
Copy The Code &

Input

cmd
n = 8

Output

cmd
3

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def integerReplacement(self, n):
"""
:type n: int
:rtype: int
"""
if n == 1:
return 0
elif n % 2 == 0:
return self.integerReplacement(n/2)+1
else:
return min(self.integerReplacement(n+1),self.integerReplacement(n-1))+1
``````
Copy The Code &

Input

cmd
n = 7

Output

cmd
4