2998. Minimum Number of Operations to Make X and Y Equal LeetCode Solution
In this guide, you will get 2998. Minimum Number of Operations to Make X and Y Equal LeetCode Solution with the best time and space complexity. The solution to Minimum Number of Operations to Make X and Y Equal problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Number of Operations to Make X and Y Equal
You are given two positive integers x and y.
In one operation, you can do one of the four following operations:
Divide x by 11 if x is a multiple of 11.
Divide x by 5 if x is a multiple of 5.
Decrement x by 1.
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.
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
Complexity Analysis
Time Complexity: O(\max(x, y))
Space Complexity: O(\max(x, y))
2998. Minimum Number of Operations to Make X and Y Equal LeetCode Solution in C++
class Solution {
public:
int minimumOperationsToMakeEqual(int x, int y) {
if (x <= y)
return y - x;
queue<int> q{{x}};
unordered_set<int> seen;
for (int ans = 0; !q.empty(); ++ans) {
for (int sz = q.size(); sz > 0; --sz) {
const int num = q.front();
q.pop();
if (num == y)
return ans;
if (seen.find(num) != seen.end())
continue;
seen.insert(num);
if (num % 11 == 0)
q.push(num / 11);
if (num % 5 == 0)
q.push(num / 5);
q.push(num - 1);
q.push(num + 1);
}
}
throw;
}
}; /* code provided by PROGIEZ */
2998. Minimum Number of Operations to Make X and Y Equal LeetCode Solution in Java
class Solution {
public int minimumOperationsToMakeEqual(int x, int y) {
if (x <= y)
return y - x;
Queue<Integer> q = new ArrayDeque<>(List.of(x));
Set<Integer> seen = new HashSet<>();
for (int ans = 0; !q.isEmpty(); ++ans) {
for (int sz = q.size(); sz > 0; --sz) {
final int num = q.poll();
if (num == y)
return ans;
if (seen.contains(num))
continue;
seen.add(num);
if (num % 11 == 0)
q.offer(num / 11);
if (num % 5 == 0)
q.offer(num / 5);
q.offer(num - 1);
q.offer(num + 1);
}
}
throw new IllegalArgumentException();
}
} // code provided by PROGIEZ
2998. Minimum Number of Operations to Make X and Y Equal LeetCode Solution in Python
class Solution:
def minimumOperationsToMakeEqual(self, x, y):
if x <= y:
return y - x
queue = collections.deque([x])
seen = set()
ans = 0
while queue:
for _ in range(len(queue)):
num = queue.popleft()
if num == y:
return ans
if num in seen:
continue
seen.add(num)
if num % 11 == 0:
queue.append(num // 11)
if num % 5 == 0:
queue.append(num // 5)
queue.append(num - 1)
queue.append(num + 1)
ans += 1 # code by PROGIEZ
