# LeetCode Integer Replacement

LeetCode Integer Replacement

Given a positive integer n and you can do operations as follow:

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

What is the minimum number of replacements needed for n to become 1?

Example 1:

```Input:
8

Output:
3

Explanation:
8 -> 4 -> 2 -> 1
```

Example 2:

```Input:
7

Output:
4

Explanation:
7 -> 8 -> 4 -> 2 -> 1
or
7 -> 6 -> 3 -> 2 -> 1```

1. 如果n是偶数，把n变成n/2
2. 如果n是奇数，把n变成n+1或者n-1

```class Solution {
private:
struct P {
long long val;
int step;
P(long long v_, int s_) :val(v_), step(s_) {};
};
public:
int integerReplacement(int n) {
P p(n, 0);
queue<P> qp;
qp.push(p);
while (!qp.empty()) {
P f = qp.front();
qp.pop();
if (f.val == 1)return f.step;
else if (f.val & 1) {
qp.push(P(f.val + 1, f.step + 1));
qp.push(P(f.val - 1, f.step + 1));
}
else {
qp.push(P(f.val / 2, f.step + 1));
}
}
return 0;
}
};
```

```class Solution {
public:
int integerReplacement(int n) {
if (n == INT_MAX)return 32;
int ans = 0;
while (n > 1) {
if ((n & 1) == 0) n >>= 1;
else if (n == 3 || ((n >> 1) & 1) == 0)--n;
else ++n;
++ans;
}
return ans;
}
};
```