Minimum Number of Operations to Make X and Y Equal solution and explanation
8 more videos on this problem
Minimum Number of Operations to Make X and Y Equal | BFS | Graph | Similar to Race CarAryan Mittal · 16:09 · 3K views
10033. Minimum Number of Operations to Make X and Y Equal | Leetcode Biweekly 121codingMohan · 15:27 · 1K views
MINIMUM NUMBER OF OPERATIONS TO MAKE X AND Y EQUAL | LEETCODE 2998 | PYTHON BFS SOLUTIONCracking FAANG · 9:03 · 794 views
Leetcode 2998: Minimum Number of Operations to Make X and Y Equal | Biweekly ContestAlgorithms Casts · 16:51 · 490 views
2998. Minimum Number of Operations to Make X and Y Equal (Leetcode Medium)Programming Live with Larry · 21:04 · 482 views
Minimum Number of Operations to Make X and Y Equal | Recursion | DP | BiWeekly 121Tech Courses · 18:02 · 338 views
100159. Minimum Number of Operations to Make X and Y Equal Q. no. 3 | Biweekly Contest 121 Leetcodesilent coder · 0:35 · 222 views
Minimum Number of Operations to Make X and Y Equal | 2998Web Mickey · 23:54 · 205 views
LeetCode 10033 - Minimum Number of Operations to Make X and Y Equal - PythonAlpha-Code · 21:24 · 115 views
The problem
You are given two positive integers x and y.
In one operation, you can do one of the four following operations:
- Divide
xby11ifxis a multiple of11. - Divide
xby5ifxis a multiple of5. - Decrement
xby1. - Increment
xby1.
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
Approach overview
Problem 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.
Approach 1: Greedy Approach
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.
def min_operations(x, y):
operations = 0
while x != y:
if x > y and x % 11 == 0:
x //= 11
elif x > y and x % 5 == 0:
x //= 5
elif x > y:
x -= 1
else:
x += 1
operations += 1
return operations
print(min_operations(54, 2))public class MinOps {
public static int minOperations(int x, int y) {
int operations = 0;
while (x != y) {
if (x > y && x % 11 == 0) {
x /= 11;
} else if (x > y && x % 5 == 0) {
x /= 5;
} else if (x > y) {
x--;
} else {
x++;
}
operations++;
}
return operations;
}
public static void main(String[] args) {
System.out.println(minOperations(54, 2));
}
}#include <iostream>
int minOperations(int x, int y) {
int ops = 0;
while (x != y) {
if (x > y && x % 11 == 0) {
x /= 11;
} else if (x > y && x % 5 == 0) {
x /= 5;
} else if (x > y) {
--x;
} else {
++x;
}
++ops;
}
return ops;
}
int main() {
std::cout << minOperations(54, 2) << std::endl;
return 0;
}function minOperations(x, y) {
let operations = 0;
while (x !== y) {
if (x > y && x % 11 === 0) {
x /= 11;
} else if (x > y && x % 5 === 0) {
x /= 5;
} else if (x > y) {
x--;
} else {
x++;
}
operations++;
}
return operations;
}
console.log(minOperations(54, 2));#include <stdio.h>
#include <math.h>
int minOperations(int x, int y) {
int operations = 0;
while (x != y) {
if (x > y && x % 11 == 0) {
x /= 11;
} else if (x > y && x % 5 == 0) {
x /= 5;
} else if (x > y) {
x -= 1;
} else {
x += 1;
}
operations++;
}
return operations;
}
int main() {
int x = 54, y = 2;
printf("%d\n", minOperations(x, y));
return 0;
}using System;
class Program {
static int MinOperations(int x, int y) {
int operations = 0;
while (x != y) {
if (x > y && x % 11 == 0) {
x /= 11;
} else if (x > y && x % 5 == 0) {
x /= 5;
} else if (x > y) {
x--;
} else {
x++;
}
operations++;
}
return operations;
}
static void Main() {
Console.WriteLine(MinOperations(54, 2));
}
}The Python implementation checks in each loop iteration whether x is divisible by 11 or 5 when greater than y, to utilize division. When x cannot be divided, it adjusts by adding or subtracting as needed until x equals y.
Time Complexity: O(log n)
Space Complexity: O(1)
Approach 2: Breadth-First Search (BFS) Approach
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.
from collections import deque
def min_operations(x, y):
if x == y:
return 0
queue = deque([x])
visited = set([x])
operations = 0
while queue:
operations += 1
for _ in range(len(queue)):
current = queue.popleft()
next_operations = [current - 1, current + 1]
if current % 11 == 0:
next_operations.append(current // 11)
if current % 5 == 0:
next_operations.append(current // 5)
for next_op in next_operations:
if next_op == y:
return operations
if 1 <= next_op <= 10000 and next_op not in visited:
visited.add(next_op)
queue.append(next_op)
return -1
print(min_operations(54, 2))import java.util.*;
public class MinOpsBFS {
static int minOperations(int x, int y) {
if (x == y) return 0;
Queue<Integer> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
queue.add(x);
visited.add(x);
int operations = 0;
while (!queue.isEmpty()) {
operations++;
int levelSize = queue.size();
for (int i = 0; i < levelSize; i++) {
int current = queue.poll();
int[] next = {current - 1, current + 1};
if (current % 11 == 0) next = extendArray(next, current / 11);
if (current % 5 == 0) next = extendArray(next, current / 5);
for (int n : next) {
if (n == y) return operations;
if (n >= 1 && !visited.contains(n)) {
queue.add(n);
visited.add(n);
}
}
}
}
return -1;
}
private static int[] extendArray(int[] arr, int value) {
int[] newArray = Arrays.copyOf(arr, arr.length + 1);
newArray[arr.length] = value;
return newArray;
}
public static void main(String[] args) {
System.out.println(minOperations(54, 2));
}
}#include <iostream>
#include <queue>
#include <unordered_set>
using namespace std;
int minOperations(int x, int y) {
if (x == y) return 0;
queue<int> bfsQueue;
unordered_set<int> visited;
bfsQueue.push(x);
visited.insert(x);
int operations = 0;
while (!bfsQueue.empty()) {
int levelSize = bfsQueue.size();
operations++;
for (int i = 0; i < levelSize; ++i) {
int current = bfsQueue.front();
bfsQueue.pop();
vector<int> nextValues = {current - 1, current + 1};
if (current % 11 == 0) nextValues.push_back(current / 11);
if (current % 5 == 0) nextValues.push_back(current / 5);
for (int next : nextValues) {
if (next == y) return operations;
if (next >= 1 && visited.find(next) == visited.end()) {
bfsQueue.push(next);
visited.insert(next);
}
}
}
}
return -1;
}
int main() {
cout << minOperations(54, 2) << endl;
return 0;
}function minOperations(x, y) {
if (x === y) return 0;
const queue = [x];
const visited = new Set([x]);
let operations = 0;
while (queue.length) {
operations += 1;
const size = queue.length;
for (let i = 0; i < size; i++) {
const current = queue.shift();
const nextOps = [current - 1, current + 1];
if (current % 11 === 0) nextOps.push(Math.floor(current / 11));
if (current % 5 === 0) nextOps.push(Math.floor(current / 5));
for (const next of nextOps) {
if (next === y) return operations;
if (next > 0 && !visited.has(next)) {
queue.push(next);
visited.add(next);
}
}
}
}
return -1;
}
console.log(minOperations(54, 2));#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int minOperations(int x, int y) {
if (x == y) return 0;
int max_val = 10000;
int queue[max_val];
int visited[max_val];
for (int i = 0; i < max_val; i++)
visited[i] = 0;
int front = 0, rear = 0;
queue[rear++] = x;
visited[x] = 1;
int operations = 0;
while (front < rear) {
int cnt = rear - front;
operations++;
for (int i = 0; i < cnt; i++) {
int current = queue[front++];
int next_values[4] = {current - 1, current + 1, current % 11 == 0 ? current / 11 : -1, current % 5 == 0 ? current / 5 : -1};
for (int j = 0; j < 4; j++) {
int next = next_values[j];
if (next == -1 || next < 1 || next >= max_val || visited[next])
continue;
if (next == y)
return operations;
queue[rear++] = next;
visited[next] = 1;
}
}
}
return -1;
}
int main() {
printf("%d\n", minOperations(54, 2));
return 0;
}using System;
using System.Collections.Generic;
class Program {
static int MinOperations(int x, int y) {
if (x == y) return 0;
Queue<int> queue = new Queue<int>();
HashSet<int> visited = new HashSet<int>();
queue.Enqueue(x);
visited.Add(x);
int operations = 0;
while (queue.Count > 0) {
operations++;
int size = queue.Count;
for (int i = 0; i < size; i++) {
int current = queue.Dequeue();
int[] nextValues = {current - 1, current + 1};
if (current % 11 == 0) Array.Resize(ref nextValues, nextValues.Length + 1); nextValues[2] = current / 11;
if (current % 5 == 0) Array.Resize(ref nextValues, nextValues.Length + 1); nextValues[3] = current / 5;
foreach (int next in nextValues) {
if (next == y) return operations;
if (next > 0 && !visited.Contains(next)) {
visited.Add(next);
queue.Enqueue(next);
}
}
}
}
return -1;
}
static void Main() {
Console.WriteLine(MinOperations(54, 2));
}
}The Python version of BFS checks reachable states through each operation level, appending valid paths to the queue for future examination until finding a match with y
Time Complexity: O(V+E)
Space Complexity: O(V)
Approach 3: Default Approach
function minimumOperationsToMakeEqual(x: number, y: number): number {
const f: Map<number, number> = new Map();
const dfs = (x: number): number => {
if (y >= x) {
return y - x;
}
if (f.has(x)) {
return f.get(x)!;
}
const a = (x % 5) + 1 + dfs((x / 5) | 0);
const b = 5 - (x % 5) + 1 + dfs(((x / 5) | 0) + 1);
const c = (x % 11) + 1 + dfs((x / 11) | 0);
const d = 11 - (x % 11) + 1 + dfs(((x / 11) | 0) + 1);
const ans = Math.min(x - y, a, b, c, d);
f.set(x, ans);
return ans;
};
return dfs(x);
}func minimumOperationsToMakeEqual(x int, y int) int {
f := map[int]int{}
var dfs func(int) int
dfs = func(x int) int {
if y >= x {
return y - x
}
if v, ok := f[x]; ok {
return v
}
a := x%5 + 1 + dfs(x/5)
b := 5 - x%5 + 1 + dfs(x/5+1)
c := x%11 + 1 + dfs(x/11)
d := 11 - x%11 + 1 + dfs(x/11+1)
f[x] = min(x-y, a, b, c, d)
return f[x]
}
return dfs(x)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(log n) Space Complexity: O(1) |
| Breadth-First Search (BFS) Approach | Time Complexity: O(V+E) Space Complexity: O(V) |
| Default Approach | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Minimum Number of Operations to Make X and Y Equal easy or hard?
Minimum Number of Operations to Make X and Y Equal is rated Medium difficulty on LeetCode. The main challenge is recognizing the problem as a shortest-path search on integers and efficiently exploring valid operations without revisiting states.
Minimum Number of Operations to Make X and Y Equal Python or Java solution
Python and Java implementations typically use a queue for BFS and a set to track visited numbers. Each step generates neighbors using +1, -1, divide by 5, and divide by 11 when divisible. The algorithm stops once Y is reached, returning the number of BFS levels as the answer.
How to solve Minimum Number of Operations to Make X and Y Equal efficiently?
Use BFS to treat each number as a graph node and apply transitions for +1, -1, divide by 5, and divide by 11 when valid. Push the starting value into a queue and explore neighbors while tracking visited numbers. The first time you reach Y gives the minimum operations because BFS processes nodes by increasing distance.
What is the best approach for Minimum Number of Operations to Make X and Y Equal?
Breadth-First Search (BFS) is the most reliable approach because the problem can be modeled as a shortest-path search where each integer value is a node and each operation is an edge. BFS explores states level by level and guarantees the first time you reach Y uses the minimum number of operations. Time complexity is O(N) with O(N) space for visited states.
What data structure is used in Minimum Number of Operations to Make X and Y Equal?
The primary data structure is a queue used for Breadth-First Search traversal. A hash set or boolean visited array tracks numbers that were already processed to prevent cycles. These structures ensure each state is explored once while maintaining optimal BFS traversal order.
What is the time complexity of Minimum Number of Operations to Make X and Y Equal?
The BFS solution runs in O(N) time where N is the range of numbers explored between X and Y. Each state is visited at most once and generates up to four transitions. A greedy division-based strategy can reduce the complexity to about O(log max(x, y)) in practice because division operations shrink the value quickly.
Is Minimum Number of Operations to Make X and Y Equal asked at Google or Amazon interviews?
Problems involving transforming numbers using minimum operations frequently appear in interviews at companies like Google, Amazon, and Meta. They test whether candidates recognize the hidden graph structure and apply BFS or dynamic programming techniques to compute the shortest transformation sequence.