Description
Given a positive integer n, you can apply one of the following operations:
- If
nis even, replacenwithn / 2. - If
nis odd, replacenwith eithern + 1orn - 1.
Return the minimum number of operations needed for n to become 1.
Examples:
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: 2Solution in Python
Approach:
- Rules:
- If n is even, divide it by 2 (n→n/2n).
- If n is odd, decide whether to increment (n+1) or decrement (n−1) to reach a smaller even number efficiently.
- Observation for Odd Numbers:
- When n is odd, the choice between n+1 and n−1 depends on which operation leads to fewer steps overall:
- n+1 is often better if n+1 becomes divisible by 4, as it allows rapid halving.
- n−1 is better if n=3 or if n−1 becomes divisible by 4.
- When n is odd, the choice between n+1 and n−1 depends on which operation leads to fewer steps overall:
- Recursive Relation:
- For even n, the result is 1+operations(n/2).
- For odd n, the result is 1+min(operations(n+1),operations(n−1)).
- Implementation:
- A recursive approach with memoization or an iterative approach (bottom-up) ensures efficiency.
Python
class Solution:
def integerReplacement(self, n: int) -> int:
# Use memoization to avoid redundant computations
memo = {}
def helper(x):
# Base case: if x is 1, no operations are needed
if x == 1:
return 0
# Check if result is already computed
if x in memo:
return memo[x]
if x % 2 == 0:
# If x is even, divide it by 2
result = 1 + helper(x // 2)
else:
# If x is odd, try both n + 1 and n - 1
result = 1 + min(helper(x + 1), helper(x - 1))
# Store the result in memo
memo[x] = result
return result
return helper(n)Explanation of the Code:
- Memoization:
- A dictionary
memois used to store results for previously computed numbers to avoid redundant calculations.
- A dictionary
- Base Case:
- If x=1, no further operations are needed, so we return 0.
- Recursive Calls:
- If x is even, directly compute 1+helper(x/2).
- If x is odd, compute both 1+helper(x+1) and 1+helper(x−1), and take the minimum.
- Result Storage:
- Store the computed result for x in the
memodictionary.
- Store the computed result for x in the
Solution in C++
C++
class Solution {
public:
int integerReplacement(int n) {
// Using long long to avoid overflow during computation
long long num = n;
int steps = 0;
// Loop until num becomes 1
while (num != 1) {
if (num % 2 == 0) {
// If the number is even, divide it by 2
num /= 2;
} else {
// If the number is odd, choose between (num + 1) or (num - 1)
// Strategy:
// - Prefer incrementing (num + 1) if num + 1 is divisible by 4 (except when num = 3)
// - Otherwise, decrement (num - 1)
if (num == 3 || ((num - 1) % 4 == 0)) {
num--;
} else {
num++;
}
}
// Increment step count for each operation
steps++;
}
return steps;
}
};Solution in Javascript
JavaScript
var integerReplacement = function(n) {
// Use a helper function to handle the logic recursively.
const helper = (num) => {
// Base case: If the number is already 1, no operations are needed.
if (num === 1) return 0;
// If the number is even, the only operation is to divide by 2.
if (num % 2 === 0) {
return 1 + helper(num / 2);
} else {
// If the number is odd, consider both +1 and -1 operations.
// Take the minimum operations needed in both cases.
return 1 + Math.min(helper(num + 1), helper(num - 1));
}
};
// Call the helper function with the initial value of `n`.
return helper(n);
};Solution in Java
Java
class Solution {
public int integerReplacement(int n) {
// Use a helper function to handle recursion, passing n as a long to avoid overflow
return helper((long) n);
}
// Helper function for recursion
private int helper(long n) {
// Base case: if n is 1, no operations are needed
if (n == 1) {
return 0;
}
// If n is even, divide it by 2
if (n % 2 == 0) {
return 1 + helper(n / 2);
} else {
// If n is odd, choose the path with the smaller number of steps
// Either increment n (n + 1) or decrement n (n - 1)
return 1 + Math.min(helper(n + 1), helper(n - 1));
}
}
}