LeetCode Solutions Blog

Minimum Number of Operations to Make X and Y Equal

Number: 3239

Difficulty: Medium

Paid? No

Problem Description

Given two positive integers x and y, find the minimum number of operations needed to make x equal to y. In one operation, you can:

Divide x by 11 (if x is a multiple of 11).
Divide x by 5 (if x is a multiple of 5).
Decrement x by 1.
Increment x by 1.

Key Insights

Since the problem asks for the minimum number of operations, a Breadth-First Search (BFS) is ideal as it explores states level by level.
The operations yield a graph where each value of x is a node, and valid operations take you to neighboring nodes.
It is crucial to keep track of visited states to avoid repeated work and infinite loops.
Although dynamic programming or memoization might be considered, using BFS directly resolves the shortest path in an unweighted state graph.

Space and Time Complexity

Time Complexity: O(N) in the worst-case scenario, where N is the range of numbers examined until reaching y. Space Complexity: O(N) due to storage of the queue and the visited set.

Solution

We use a BFS approach where each node represents a current value of x and the level represents the number of operations performed. Starting from x, we explore all possible next states: if x is divisible by 11 or 5, we also consider the state resulting from the division, along with the states x+1 and x-1. We use a visited set to ensure that each state is processed only once, thereby preventing cycles and redundant work. Once y is reached, the current level in the BFS represents the minimum number of operations required.

Code Solutions

from collections import deque

def minOperations(x, y):
    # Edge case: if x is already equal to y, no operations are needed.
    if x == y:
        return 0
    
    # Initialize the BFS queue with tuple (current value, steps taken)
    queue = deque([(x, 0)])
    visited = set([x])
    
    while queue:
        current, steps = queue.popleft()
        
        # Check if the current value matches y
        if current == y:
            return steps
        
        # List of neighbors (possible next states)
        neighbors = []
        # Operation: if divisible by 11, divide by 11.
        if current % 11 == 0:
            neighbors.append(current // 11)
        # Operation: if divisible by 5, divide by 5.
        if current % 5 == 0:
            neighbors.append(current // 5)
        # Operation: increment.
        neighbors.append(current + 1)
        # Operation: decrement.
        neighbors.append(current - 1)
        
        for next_val in neighbors:
            # We consider only positive values as only positive integers are allowed.
            if next_val > 0 and next_val not in visited:
                visited.add(next_val)
                queue.append((next_val, steps + 1))
    
    # If no solution is found (theoretically should not happen) return -1.
    return -1

# Example Usage
print(minOperations(26, 1))  # Output: 3
print(minOperations(54, 2))  # Output: 4
print(minOperations(25, 30)) # Output: 5