# Minimum Number of Operations to Make X and Y Equal
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-number-of-operations-to-make-x-and-y-equal)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-operations-to-make-x-and-y-equal
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Memoization](https://scaleengineer.com/dsa/patterns/memoization)
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Companies:** [Groww](https://scaleengineer.com/companies/groww)
---
## Problem
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.

**Example 1:**

**Input:** x = 26, y = 1
**Output:** 3
**Explanation:** We can make 26 equal to 1 by applying the following operations: 
1. Decrement x by 1
2. Divide x by 5
3. Divide x by 5
It can be shown that 3 is the minimum number of operations required to make 26 equal to 1.

**Example 2:**

**Input:** x = 54, y = 2
**Output:** 4
**Explanation:** We can make 54 equal to 2 by applying the following operations: 
1. Increment x by 1
2. Divide x by 11 
3. Divide x by 5
4. Increment x by 1
It can be shown that 4 is the minimum number of operations required to make 54 equal to 2.

**Example 3:**

**Input:** x = 25, y = 30
**Output:** 5
**Explanation:** We can make 25 equal to 30 by applying the following operations: 
1. Increment x by 1
2. Increment x by 1
3. Increment x by 1
4. Increment x by 1
5. Increment x by 1
It can be shown that 5 is the minimum number of operations required to make 25 equal to 30.

**Constraints:**

* `1 <= x, y <= 104`

# Approaches
## Brute-Force Recursion
A brute-force approach involves exploring every possible sequence of operations from `x` until `y` is reached. This can be framed as a recursive solution. We define a function that represents the state (the current number) and recursively calls itself for all possible next states that can be reached in one operation. The minimum of the results of these recursive calls is the answer for the current state.
**Time:** Exponential, roughly O(4^N), where N is the number of operations. The same states are computed multiple times. · **Space:** O(D), where D is the maximum depth of the recursion. In the worst case, this can be very large, leading to a `StackOverflowError`.
**Pros:** Simple to understand the basic concept of exploring all paths.
**Cons:** Extremely inefficient due to re-computation of the same subproblems.; Will result in a 'Time Limit Exceeded' (TLE) error for all but the smallest inputs.; Prone to infinite recursion and stack overflow without careful (and complex) state management.
### Explanation
This method models the problem as a state graph where each number is a node and each operation is an edge. The function `solve(currentX)` attempts to find the shortest path from `currentX` to `y`. It does this by trying every possible move: decrementing to `currentX - 1`, incrementing to `currentX + 1`, and, if applicable, dividing by 5 or 11. It then adds 1 to the result of the best move. The issue is that the same intermediate numbers (e.g., `solve(10)`) will be calculated over and over again through different paths, leading to an exponential number of calls.

```java
// This is a conceptual representation. It will not pass due to performance issues.
public int solve(int currentX, int y) {
    if (currentX == y) {
        return 0;
    }
    // A basic pruning to avoid going too far away from the target.
    // A robust solution would need more complex bounds.
    if (currentX <= 0 || currentX > 20000) {
        return 1_000_000_000; 
    }

    // Explore all paths recursively
    int op1 = 1 + solve(currentX - 1, y); // Decrement
    int op2 = 1 + solve(currentX + 1, y); // Increment
    
    int minOps = Math.min(op1, op2);

    if (currentX % 5 == 0) {
        minOps = Math.min(minOps, 1 + solve(currentX / 5, y));
    }
    if (currentX % 11 == 0) {
        minOps = Math.min(minOps, 1 + solve(currentX / 11, y));
    }
    
    return minOps;
}
```
### Algorithm
1. Define a recursive function, say `solve(currentX)`, that calculates the minimum operations from `currentX` to `y`.
2. The base case for the recursion is when `currentX == y`, in which case the function returns 0.
3. In the recursive step, the function explores all four possible operations (increment, decrement, divide by 5, divide by 11) by making a recursive call for each valid resulting state.
4. The function returns `1 +` the minimum value returned by these recursive calls.
5. To prevent infinite loops (e.g., `x -> x+1 -> x`), this naive approach would require passing a set of visited nodes for the current path, making it even more complex and inefficient.

## Recursion with Memoization (Top-Down DP)
To fix the massive redundancy of the brute-force approach, we can use memoization, a dynamic programming technique. We store the result for each number we compute, so that if we need to compute it again, we can just look up the answer. This is essentially a Depth-First Search (DFS) on the state graph.
**Time:** O(S), where S is the number of states explored. In the worst case, this is proportional to the initial value of `x`. · **Space:** O(S) for the memoization table and O(S) for the recursion stack, where S is the number of states explored. This is roughly O(x).
**Pros:** Drastically more efficient than brute-force recursion.; Guarantees that each state is computed only once.
**Cons:** While it fixes the re-computation issue, it is still a recursive approach.; Can suffer from `StackOverflowError` if the recursion depth becomes too large, which can happen if `x` is much larger than `y`.
### Explanation
This approach enhances the recursive solution by adding a cache (e.g., a `HashMap`) to store the minimum operations for any number `i` once computed. This prevents re-computation and reduces the time complexity from exponential to linear in the number of states. However, as a DFS-based approach, it explores one path to its full depth before backtracking. If `x` is significantly larger than `y`, a path involving many decrements (`x -> x-1 -> x-2 ...`) could lead to a very deep recursion stack, risking a `StackOverflowError`.

```java
class Solution {
    private Map<Integer, Integer> memo;

    public int minimumOperations(int x, int y) {
        memo = new HashMap<>();
        return solve(x, y);
    }

    private int solve(int currentX, int targetY) {
        if (currentX <= targetY) {
            return targetY - currentX;
        }
        if (memo.containsKey(currentX)) {
            return memo.get(currentX);
        }

        // Path 1: Decrement by 1.
        // This also serves as a baseline path cost.
        int res = 1 + solve(currentX - 1, targetY);

        // Path 2: Divide by 11, if possible.
        if (currentX % 11 == 0) {
            res = Math.min(res, 1 + solve(currentX / 11, targetY));
        }

        // Path 3: Divide by 5, if possible.
        if (currentX % 5 == 0) {
            res = Math.min(res, 1 + solve(currentX / 5, targetY));
        }
        
        // Path 4 & 5: Increment first, then divide.
        // This is tricky in DFS. A better way is to consider reaching the nearest multiples.
        // Cost to reach the nearest multiple of 11 (by decrementing) + 1 (for division) + result from there.
        res = Math.min(res, (currentX % 11) + 1 + solve(currentX / 11, targetY));
        // Cost to reach the nearest multiple of 11 (by incrementing) + 1 (for division) + result from there.
        res = Math.min(res, (11 - (currentX % 11)) + 1 + solve(currentX / 11 + 1, targetY));

        // Similarly for 5.
        res = Math.min(res, (currentX % 5) + 1 + solve(currentX / 5, targetY));
        res = Math.min(res, (5 - (currentX % 5)) + 1 + solve(currentX / 5 + 1, targetY));

        memo.put(currentX, res);
        return res;
    }
}
```
*Note: The provided code demonstrates a more optimized recursive strategy than a simple 4-way branching DFS, but BFS remains superior in robustness.*
### Algorithm
1. Use a hash map or an array, `memo`, to store the results of subproblems that have already been solved.
2. The recursive function, `solve(currentX)`, first checks if the result for `currentX` exists in `memo`. If it does, it returns the stored value immediately.
3. If the value is not in `memo`, it computes the result by recursively calling itself for all valid next states, just like the brute-force approach.
4. Before returning the computed result, it stores it in `memo` with `currentX` as the key.
5. An important optimization: if `currentX <= y`, the shortest path is to simply increment `currentX` until it reaches `y` or decrement `y` until it reaches `currentX`. The number of operations is `y - currentX`.

## Breadth-First Search (BFS)
Since this is a shortest path problem on an unweighted graph (all operations have a cost of 1), Breadth-First Search (BFS) is the most suitable and robust algorithm. BFS explores the state graph level by level, guaranteeing that the first time we reach the target `y`, it will be via a path with the minimum number of operations.
**Time:** O(S + E), where S is the number of states (nodes) and E is the number of transitions (edges). Since each node has at most 4 edges, this simplifies to O(S). The number of states is bounded by the values explored, roughly O(x). · **Space:** O(S), where S is the number of states explored. This is for the queue and the distance map. In the worst case, this is proportional to `x`.
**Pros:** Guaranteed to find the shortest path in an unweighted graph.; It is an iterative approach, so it avoids the risk of `StackOverflowError`.; Generally the most efficient and reliable method for this category of problems.
**Cons:** May use more memory than a highly optimized recursive solution if the number of states at each level is large.; Can be slightly more code to write compared to a simple recursive function.
### Explanation
We start the search from `x`. A queue holds the numbers to visit, and a map or array stores the number of operations (distance) to reach each number from `x`. The distance map also handily doubles as a `visited` set, preventing cycles and redundant processing.

We begin by adding `x` to the queue with 0 operations. Then, we repeatedly extract a number from the queue, explore its neighbors (the numbers resulting from the four operations), and add any unvisited neighbors back into the queue with an incremented operation count. Because BFS explores layer by layer, the first time we encounter `y`, we are guaranteed to have done so in the minimum number of steps.

```java
import java.util.Queue;
import java.util.LinkedList;
import java.util.Map;
import java.util.HashMap;

class Solution {
    public int minimumOperations(int x, int y) {
        if (x <= y) {
            return y - x;
        }

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(x);
        
        Map<Integer, Integer> dist = new HashMap<>();
        dist.put(x, 0);

        while (!queue.isEmpty()) {
            int current = queue.poll();
            int currentDist = dist.get(current);

            if (current == y) {
                return currentDist;
            }

            // Try all 4 operations
            int[] nextStates = {current - 1, current + 1};
            for (int next : nextStates) {
                if (next > 0 && !dist.containsKey(next)) {
                    dist.put(next, currentDist + 1);
                    queue.offer(next);
                }
            }

            if (current % 11 == 0) {
                int next = current / 11;
                if (!dist.containsKey(next)) {
                    dist.put(next, currentDist + 1);
                    queue.offer(next);
                }
            }

            if (current % 5 == 0) {
                int next = current / 5;
                if (!dist.containsKey(next)) {
                    dist.put(next, currentDist + 1);
                    queue.offer(next);
                }
            }
        }
        
        return -1; // Should not be reached given the problem constraints
    }
}
```
### Algorithm
1. Handle the base case: if `x <= y`, the only optimal way is to increment `x` `y-x` times. Return `y-x`.
2. For the main case `x > y`, initialize a queue for BFS and add the starting number `x`.
3. Use a map or an array `dist` to store the minimum operations to reach any number. Initialize `dist[x] = 0`. This map also serves as a `visited` set.
4. While the queue is not empty, dequeue a number `current`.
5. If `current == y`, we have found the shortest path. Return `dist[current]`.
6. Otherwise, generate all possible next states from `current`: `current - 1`, `current + 1`, `current / 5`, `current / 11`.
7. For each valid `next` state that has not been visited (i.e., not in `dist`), update its distance `dist[next] = dist[current] + 1` and enqueue it.

# Solutions
### Java

```java
class Solution {
private
  Map<Integer, Integer> f = new HashMap<>();
private
  int y;
public
  int minimumOperationsToMakeEqual(int x, int y) {
    this.y = y;
    return dfs(x);
  }
private
  int dfs(int x) {
    if (y >= x) {
      return y - x;
    }
    if (f.containsKey(x)) {
      return f.get(x);
    }
    int ans = x - y;
    int a = x % 5 + 1 + dfs(x / 5);
    int b = 5 - x % 5 + 1 + dfs(x / 5 + 1);
    int c = x % 11 + 1 + dfs(x / 11);
    int d = 11 - x % 11 + 1 + dfs(x / 11 + 1);
    ans = Math.min(ans, Math.min(a, Math.min(b, Math.min(c, d))));
    f.put(x, ans);
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumOperationsToMakeEqual(int x, int y) {
    unordered_map<int, int> f;
    function<int(int)> dfs = [&](int x) {
      if (y >= x) {
        return y - x;
      }
      if (f.count(x)) {
        return f[x];
      }
      int a = x % 5 + 1 + dfs(x / 5);
      int b = 5 - x % 5 + 1 + dfs(x / 5 + 1);
      int c = x % 11 + 1 + dfs(x / 11);
      int d = 11 - x % 11 + 1 + dfs(x / 11 + 1);
      return f[x] = min({x - y, a, b, c, d});
    };
    return dfs(x);
  }
};

```

### Python

```python
class Solution:
    def minimumOperationsToMakeEqual(self, x: int, y: int) -> int: @ cache def dfs(x: int) -> int: if y >= x: return y - x ans = x - y ans = min(ans, x % 5 + 1 + dfs(x // 5)) ans = min(ans, 5 - x % 5 + 1 + dfs(x // 5 + 1)) ans = min(ans, x % 11 + 1 + dfs(x // 11)) ans = min(ans, 11 - x % 11 + 1 + dfs(x // 11 + 1)) return ans return dfs(x)

```