Integer Replacement - Leetcode Solution

Problem Statement:

Given a positive integer n, you can do the following operations:

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

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: 2

Solution:

To solve this problem, we can use a recursive approach. If the given integer is already 1, return 0 as no operations are required. Else, if the given integer is even, we can divide it by 2 and recursively call the function with the new integer. If the given integer is odd, we can either add 1 or subtract 1 and recursively call the function with the new integer.

To optimize the solution, we can use memoization to store the minimum number of operations required for each integer that has been processed. This will help us avoid redundant calculations and improve the time complexity of the algorithm.

Algorithm:

1. If n == 1, return 0.
2. If n is even, return 1 + integerReplacement(n/2).
3. Else, return 1 + min(integerReplacement(n+1), integerReplacement(n-1)).
4. Use memoization to store the minimum number of operations required for each integer.

Code in Python:

class Solution: def init(self): self.memo = {}

def integerReplacement(self, n: int) -> int:
    if n == 1:
        return 0
    
    if n in self.memo:
        return self.memo[n]
    
    if n % 2 == 0:
        self.memo[n] = 1 + self.integerReplacement(n//2)
    else:
        self.memo[n] = 1 + min(self.integerReplacement(n+1), self.integerReplacement(n-1))
    
    return self.memo[n] 

Time Complexity:

The time complexity of the algorithm is O(log n) as we are processing only half of the numbers at each iteration.

Space Complexity:

The space complexity of the algorithm is also O(log n) as we are using memoization to store the minimum number of operations required for each integer.

1