# Integer Replacement Problem

## Description

LeetCode Problem 397.

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

• If n is even, replace n with n / 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:

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

Example 2:

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

Example 3:

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

Constraints:

• 1 <= n <= 2^31 - 1

## Sample C++ Code

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
private:
unordered_map<int, int> visited;

public:
int integerReplacement(int n) {
if (n == 1) { return 0; }
if (visited.count(n) == 0) {
if (n & 1 == 1) {
visited[n] = 2 + min(integerReplacement(n / 2), integerReplacement(n / 2 + 1));
} else {
visited[n] = 1 + integerReplacement(n / 2);
}
}
return visited[n];
}
};
``````