algoadvance

The problem requires you to write a function that takes a positive integer n and returns the minimum number of replacements needed for n to become 1. The replacements can be:

  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.

Clarifying Questions

To ensure full understanding of the problem, here are some clarifications:

  1. Input types: Can we assume the input will always be a positive integer?
    • Yes, the problem guarantees that n is a positive integer.
  2. Output types: Should the output always be an integer representing the minimum steps required?
    • Yes, the output should be a non-negative integer.

Strategy

The problem can be approached using a Breadth-First Search (BFS) for optimality since BFS finds the shortest path in an unweighted graph and in this case, we can think of each number as a graph node.

  1. Use BFS:
    • Initialize a queue with the first element (n, 0) where 0 represents the current depth (number of steps taken).
    • Use a set to keep track of visited numbers to avoid cycles.
    • While the queue is not empty:
      • Dequeue the first element.
      • If the dequeued number is 1, return the steps taken so far.
      • If the number is even, enqueue (number / 2, steps + 1).
      • If the number is odd, enqueue both (number + 1, steps + 1) and (number - 1, steps + 1) unless those values have been visited.
    • This ensures that we find the minimum steps to reach 1.

Code

Here’s the implementation of the explained strategy:

from collections import deque

def integerReplacement(n: int) -> int:
    # Edge case, if already n is 1
    if n == 1:
        return 0
    
    queue = deque([(n, 0)])
    visited = set([n])
    
    while queue:
        current, steps = queue.popleft()
        
        if current == 1:
            return steps
        
        next_steps = steps + 1
        
        if current % 2 == 0:
            next_num = current // 2
            if next_num not in visited:
                visited.add(next_num)
                queue.append((next_num, next_steps))
        else:
            next_num1 = current + 1
            next_num2 = current - 1
            if next_num1 not in visited:
                visited.add(next_num1)
                queue.append((next_num1, next_steps))
            if next_num2 not in visited:
                visited.add(next_num2)
                queue.append((next_num2, next_steps))

Time Complexity

The time complexity for this solution is O(log n):

The space complexity is O(log n) as well due to the nature of the BFS kept in the queue and the visited set maintaining states of up to log n due to the halving steps.

Try our interview co-pilot at AlgoAdvance.com