algoadvance

Leetcode 397. Integer Replacement

Problem Statement

397. Integer Replacement

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 find the minimum number of replacements needed for n to become 1.

Example:

Input: 8
Output: 3
Explanation: 8 -> 4 -> 2 -> 1

Input: 7
Output: 4
Explanation: 7 -> 8 -> 4 -> 2 -> 1 or 7 -> 6 -> 3 -> 2 -> 1

Clarifying Questions

1. Can n be guaranteed to be a positive integer?
   • Yes, n is guaranteed to be a positive integer based on the problem statement.
2. Is there a limit to the size of n?
   • The problem statement does not specify a limit, but given it is a LeetCode problem, n could be up to 2^31 - 1 for practical constraints.

Strategy

1. Recursive Solution with Memoization: Use a recursive approach to solve the problem by breaking it down into subproblems. If n is even, the operation is straightforward (n / 2). If n is odd, you decide between n + 1 and n - 1, choosing the one that leads to a smaller number of steps. Memoization helps store the results of already computed values to avoid redundant calculations.

2. Iterative Solution: Alternatively, employ an iterative approach to use a queue (or deque) to perform a BFS (Breadth-First Search) from n to 1. This ensures that we always find the shortest path.

Code

Here we’ll implement a recursive solution with memoization:

import java.util.HashMap;
import java.util.Map;

public class IntegerReplacement {
    private Map<Integer, Integer> memo = new HashMap<>();
    
    public int integerReplacement(int n) {
        if (n == 1) {
            return 0;
        }
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        
        int steps;
        if (n % 2 == 0) {
            steps = 1 + integerReplacement(n / 2);
        } else {
            steps = 1 + Math.min(integerReplacement(n + 1), integerReplacement(n - 1));
        }
        
        memo.put(n, steps);
        return steps;
    }
    
    public static void main(String[] args) {
        IntegerReplacement solution = new IntegerReplacement();
        System.out.println(solution.integerReplacement(8)); // Output: 3
        System.out.println(solution.integerReplacement(7)); // Output: 4
    }
}

Time Complexity

• Recursive Solution with Memoization:
  • Time Complexity: O(log n), as we are reducing the problem size either by half (in case of even n) or adjusting slightly (in case of odd n), and memoization ensures each value is computed at most once.
  • Space Complexity: O(log n) for the recursion stack and O(log n) for the memoization map.

This solution efficiently computes the minimum replacement operations, leveraging the memoization technique to store and reuse already computed values.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?