You are given two positive integers x and y.
In one operation, you can do one of the four following operations:
x by 11 if x is a multiple of 11.x by 5 if x is a multiple of 5.x by 1.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 <= 104Problem Overview: You are given two integers x and y. The goal is to transform x into y using the minimum number of operations. Allowed operations include dividing by 5 or 11 when divisible, or adjusting the value by +1 or -1. The challenge is finding the shortest sequence of operations without exploring unnecessary states.
Approach 1: Greedy Adjustment + Division (Time: O(log max(x,y)), Space: O(1))
The greedy idea is to reduce large numbers quickly using division because division shrinks the value much faster than repeated decrements. When x > y, try to make x divisible by 11 or 5 using the fewest +1 or -1 adjustments, then perform the division. Each division significantly reduces the search space. If x <= y, the best strategy is simply applying +1 operations until the values match. This method avoids exploring every possible path and works efficiently for large values.
Approach 2: Breadth-First Search (BFS) (Time: O(N), Space: O(N))
Model the problem as a shortest path search where each integer value represents a node in a graph. From a node v, you can move to v+1, v-1, v/5 if divisible, and v/11 if divisible. Using Breadth-First Search guarantees the first time you reach y is through the minimum number of operations. A queue stores the next states to process while a visited set prevents revisiting numbers. BFS works well when the search range is bounded and guarantees correctness for all cases.
Some implementations also cache results with memoization or structure the transitions similarly to dynamic programming to avoid recomputation. However, BFS already ensures minimal operations due to level-by-level exploration.
Recommended for interviews: The BFS approach is the safest answer because it models the problem directly as a shortest-path search and guarantees correctness. Interviewers often expect you to recognize the implicit graph and apply BFS. The greedy strategy is more optimized and shows deeper insight into how division operations reduce the search space, but BFS demonstrates clear reasoning and correctness under all constraints.
The greedy strategy involves reducing the number in a way that it quickly converges towards the target. By greedily dividing by 11 or 5 whenever possible, we attempt to minimize the number rapidly before fine-tuning through increments or decrements.
This method prioritizes division operations first because they have a more significant effect on the number's value, bringing it closer to the desired value faster than increment or decrement steps.
The code checks conditions in a loop to differentiate between division and increment/decrement operations.
If x is larger than y and can be evenly divided by 11, it performs that division since it's the largest divisor. Otherwise, it checks divisibility by 5, performs subtractions if still larger than y, or adds if smaller.
Time Complexity: O(log n), where n is the maximum of x or y. Each division operation halves the problem size.
Space Complexity: O(1), as only a fixed amount of additional storage is used.
This approach treats each possible value of x as a node in a graph, with edges representing the operations that can be performed. Using BFS allows exploring shorter paths first, ensuring the fewest operations are discovered to convert x to y. The BFS traverses the graph until we locate the node corresponding to y, returning the level it appears on as the minimal operations count.
The BFS approach uses a queue to manage states of x, exploring each one by applying all possible operations. It marks states as visited to avoid re-processing, efficiently identifying the shortest path through levels in the graph
Time Complexity: O(V+E), where V is the vertex count (possible values of x) and E is edge operations.
Space Complexity: O(V) for tracking visited states and queue storage.
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(log n), where n is the maximum of x or y. Each division operation halves the problem size. Space Complexity: O(1), as only a fixed amount of additional storage is used. |
| Breadth-First Search (BFS) Approach | Time Complexity: O(V+E), where V is the vertex count (possible values of x) and E is edge operations. Space Complexity: O(V) for tracking visited states and queue storage. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Adjustment + Division | O(log max(x,y)) | O(1) | Best when large numbers allow frequent division by 5 or 11 |
| Breadth-First Search (BFS) | O(N) | O(N) | General case when you need guaranteed minimum operations |
Minimum Number of Operations to Make X and Y Equal | BFS | Graph | Similar to Race Car • Aryan Mittal • 3,689 views views
Watch 9 more video solutions →Practice Minimum Number of Operations to Make X and Y Equal with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor