# 397. 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
``````

``````class Solution {
public:
int integerReplacement(int n) {
if (n == 1) return 0;
if (n % 2 == 0) return 1 + integerReplacement(n / 2);
else {
long long t = n;
return 2 + min(integerReplacement((t + 1) / 2), integerReplacement((t - 1) / 2));
}
}
};
``````

15 -> 16 -> 8 -> 4 -> 2 -> 1

15 -> 14 -> 7 -> 6 -> 3 -> 2 -> 1

``````class Solution {
public:
int integerReplacement(int n) {
long long t = n;
int cnt = 0;
while (t > 1) {
++cnt;
if (t & 1) {
if ((t & 2) && (t != 3)) ++t;
else --t;
} else {
t >>= 1;
}
}
return cnt;
}
};
``````

https://discuss.leetcode.com/topic/58655/0ms-cpp-solution

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation