Scale Engineer

Minimum Number of Operations to Make X and Y Equal

Med
#2666Time: 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`.1 company
Patterns
Dynamic ProgrammingMemoization
Algorithms
Breadth-First Search
Companies
Groww

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

// 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;}

Complexity

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`.

Trade-offs

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.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem