Problem#
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
.
Examples#
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
Solution#
Method 1 – Greedy with Recursion and Memoization#
Intuition#
The problem can be solved by recursively reducing n
to 1, always choosing the operation that leads to the minimum steps. For even numbers, divide by 2. For odd numbers, try both n+1
and n-1
and pick the minimum. Memoization avoids redundant calculations.
Approach#
If n
is 1, return 0 (base case).
If n
is even, recursively call with n/2
.
If n
is odd, recursively call with both n+1
and n-1
, take the minimum.
Use a cache (memoization) to store results for each n
to avoid recomputation.
Return the minimum number of steps.
Code#
Cpp
Go
Java
Kotlin
Python
Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
unordered_map< long , int > memo;
public :
int integerReplacement(int n) {
return helper (n);
}
int helper (long n) {
if (n == 1 ) return 0 ;
if (memo.count(n)) return memo[n];
int ans;
if (n % 2 == 0 ) {
ans = 1 + helper(n / 2 );
} else {
ans = 1 + min(helper(n + 1 ), helper(n - 1 ));
}
memo[n] = ans;
return ans;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
type Solution struct {
memo map [int ]int
}
func (s * Solution ) integerReplacement (n int ) int {
if s .memo == nil {
s .memo = make(map [int ]int )
}
if n == 1 {
return 0
}
if v , ok := s .memo [n ]; ok {
return v
}
var ans int
if n % 2 == 0 {
ans = 1 + s .integerReplacement (n / 2 )
} else {
ans = 1 + min(s .integerReplacement (n + 1 ), s .integerReplacement (n - 1 ))
}
s .memo [n ] = ans
return ans
}
func min(a , b int ) int {
if a < b {
return a
}
return b
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
private Map< Long, Integer> memo = new HashMap<> ();
public int integerReplacement (int n) {
return helper((long )n);
}
private int helper (long n) {
if (n == 1) return 0;
if (memo.containsKey (n)) return memo.get (n);
int ans;
if (n % 2 == 0) {
ans = 1 + helper(n / 2);
} else {
ans = 1 + Math.min (helper(n + 1), helper(n - 1));
}
memo.put (n, ans);
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
private val memo = mutableMapOf<Long, Int>()
fun integerReplacement (n: Int): Int {
return helper(n.toLong())
}
private fun helper (n: Long): Int {
if (n == 1L ) return 0
memo[n]?. let { return it }
val ans = if (n % 2 == 0L ) {
1 + helper(n / 2 )
} else {
1 + minOf(helper(n + 1 ), helper(n - 1 ))
}
memo[n] = ans
return ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution :
def integerReplacement (self, n: int) -> int:
memo: dict[int, int] = {}
def helper (x: int) -> int:
if x == 1 :
return 0
if x in memo:
return memo[x]
if x % 2 == 0 :
ans = 1 + helper(x // 2 )
else :
ans = 1 + min(helper(x + 1 ), helper(x - 1 ))
memo[x] = ans
return ans
return helper(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
use std::collections::HashMap;
impl Solution {
pub fn integer_replacement (n: i32 ) -> i32 {
fn helper (x: i64 , memo: & mut HashMap< i64 , i32 > ) -> i32 {
if x == 1 {
return 0 ;
}
if let Some(& v) = memo.get(& x) {
return v;
}
let ans = if x % 2 == 0 {
1 + helper(x / 2 , memo)
} else {
1 + std::cmp::min(helper(x + 1 , memo), helper(x - 1 , memo))
};
memo.insert(x, ans);
ans
}
helper(n as i64 , & mut HashMap::new())
}
}
Complexity#
Time: O(log n)
— Each recursive call reduces n
by half or by 1, and memoization ensures each value is computed once.
Space: O(log n)
— For the recursion stack and memoization storage.