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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Number of Operations to Make X and Y Equal

Difficulty: Medium

Problem Description

You are given two positive integers x and y. In one operation, you can do one of the four following operations:

  1. Divide x by 11 if x is a multiple of 11.
  2. Divide x by 5 if x is a multiple of 5.
  3. Decrement x by 1.
  4. Increment x by 1.

Return the minimum number of operations required to make x and y equal.

Key Insights

  • The operations allow both decrementing and incrementing, which means we can reach any value between x and y.
  • Using division operations can significantly reduce the value of x when applicable, providing a more efficient path to y.
  • A breadth-first search (BFS) approach can effectively explore the minimum operations needed to reach from x to y, using a queue to process states.

Space and Time Complexity

Time Complexity: O(N) where N is the maximum distance between x and y. Space Complexity: O(N) for storing the states in the BFS queue.

Solution

The solution uses a breadth-first search (BFS) approach to explore all possible states of x starting from the initial value. The BFS will explore all valid operations and track the number of operations taken to reach each state. The goal is to find the minimum number of operations to reach y from x.

We will use a queue to manage our states and a set to track visited states to avoid cycles. Starting from x, we will apply all valid operations, pushing new states into the queue along with the operation count until we reach y.

Code Solutions

from collections import deque

def min_operations(x: int, y: int) -> int:
    # BFS initialization
    queue = deque([(x, 0)])  # (current value, operations count)
    visited = set([x])  # To track visited states

    while queue:
        current, operations = queue.popleft()

        # If we reached y, return the number of operations
        if current == y:
            return operations

        # Generate possible next states
        next_states = []
        if current > 1:
            next_states.append(current - 1)  # Decrement
        next_states.append(current + 1)      # Increment
        if current % 11 == 0:
            next_states.append(current // 11)  # Divide by 11
        if current % 5 == 0:
            next_states.append(current // 5)   # Divide by 5

        # Process next states
        for next_state in next_states:
            if 0 < next_state <= 10000 and next_state not in visited:
                visited.add(next_state)
                queue.append((next_state, operations + 1))

    return -1  # In case no solution found
← Back to All Questions