We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Integer Replacement

Number: 397

Difficulty: Medium

Paid? No

Companies: Google, Bloomberg, Baidu

Problem Description

Given a positive integer n, perform the following operations until n becomes 1:

  • If n is even, replace n with n / 2.
  • If n is odd, you can either replace n with n + 1 or n - 1. The task is to determine the minimum number of operations required to reduce n to 1.

Key Insights

  • For even numbers, the optimal step is always to divide by 2.
  • For odd numbers, deciding whether to add 1 or subtract 1 is critical. In most cases, moving towards an even number with more trailing zeros in its binary representation is beneficial.
  • A special case exists when n equals 3; subtracting 1 is preferable to avoid extra steps.
  • Using recursion with memoization or dynamic programming helps avoid recomputation of subproblems.

Space and Time Complexity

Time Complexity: O(log n) on average, due to the division steps and memoization reducing repeated work. Space Complexity: O(log n), accounting for the recursion stack and memoization storage.

Solution

The solution uses a recursive approach with memoization to store previously computed results. For every call:

  • If n is even, it recursively computes the steps for n / 2.
  • If n is odd, it recursively computes the steps for both n + 1 and n - 1 and takes the minimum of the two.
  • A special check for n = 3 is added to optimize the decision process. This strategy ensures that each unique number is computed only once, leading to significant performance improvements through memoization.

Code Solutions

def integerReplacement(n: int) -> int:
    # Dictionary to store computed results for memoization
    memo = {}
    
    def helper(current: int) -> int:
        # Base case: when the number reaches 1, no more operations are needed.
        if current == 1:
            return 0
        # Return the result if already computed.
        if current in memo:
            return memo[current]
        # If the current number is even, divide by 2.
        if current % 2 == 0:
            memo[current] = 1 + helper(current // 2)
        else:
            # Special handling for 3 to avoid extra steps.
            if current == 3:
                memo[current] = 1 + helper(current - 1)
            else:
                # For odd numbers, explore both n + 1 and n - 1.
                memo[current] = 1 + min(helper(current + 1), helper(current - 1))
        return memo[current]
    
    return helper(n)

# Example usage:
print(integerReplacement(8))  # Expected output: 3
← Back to All Questions