algoadvance

Leetcode 397. Integer Replacement

Problem Statement

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

  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.

Your task is to return the minimum number of replacements needed for n to become 1.

For example:

Clarifying Questions

  1. Can n be very large?
    • Yes, n can be as large as 2^31 - 1.
  2. Should the solution minimize memory usage or is there a specific time constraint?
    • Typically, solutions should balance time and space complexity, but time complexity will be our primary focus.

Strategy

  1. Use a recursive approach with memoization to minimize recomputation.
  2. If n is even, the problem reduces to integerReplacement(n / 2) + 1.
  3. If n is odd, the problem has two subcases:
    • Replace n with n + 1 and solve for n + 1
    • Replace n with n - 1 and solve for n - 1
  4. Use memoization to store results of subproblems to avoid redundant calculations.
  5. Recursion should be optimal given the constraints.

Time Complexity

Code

Here’s the C++ implementation:

#include <unordered_map>

class Solution {
public:
    int integerReplacement(int n) {
        return helper(n);
    }
    
private:
    std::unordered_map<long long, int> memo;
    
    int helper(long long n) {
        if (n == 1) return 0;
        if (memo.find(n) != memo.end()) return memo[n];
        
        if (n % 2 == 0) {
            memo[n] = 1 + helper(n / 2);
        } else {
            memo[n] = 1 + std::min(helper(n + 1), helper(n - 1));
        }
        
        return memo[n];
    }
};

Explanation:

  1. Base Case: If n is 1, the function returns 0 since no operations are needed.
  2. Memoization: A map memo is used to store previously computed results for subproblems.
  3. Even n: If n is even, the function recursively solves for n/2 and adds 1 to account for the operation.
  4. Odd n: If n is odd, it solves both n+1 and n-1 cases recursively, taking the minimum of the two results and adds 1 to account for the operation.
  5. Recursive Function: Uses a private helper function that performs the recursion and memoization.

This code efficiently computes the minimum number of replacements for any given n, leveraging memoization to ensure optimal performance.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI