|
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.
Examples:
Input: x = 26, y = 1
Output: 3
Explanation: We can make 26 equal to 1 by applying the following operations:
- Decrement x by 1
- Divide x by 5
- Divide x by 5
It can be shown that 3 is the minimum number of operations required to make 26 equal to 1.
Input: x = 54, y = 2
Output: 4
Explanation: We can make 54 equal to 2 by applying the following operations:
- Increment x by 1
- Divide x by 11
- Divide x by 5
- Increment x by 1
It can be shown that 4 is the minimum number of operations required to make 54 equal to 2.
Approach:
We need to check for 5 ways in our recursive calls :
- Just abs diff of x & y can be ans. So initialise res = abs(x – y)
- We may go to multiple of 5 which is smaller than x. This can be achieved by just subtracting x%5 from x and divide x by 5. Here total operations = x%5 ( this many time decreament ) + 1( for division by 5).
- We may go to multiple of 5 which is larger than x. This can be achieved by just adding (5 – x%5) to x and then divid x by 5. Here total operations = 5 – x%5 ( this many time increment ) + 1( for division by 5).
- We may go to multiple of 11 which is smaller than x. This can be achieved by just subtracting x%11 from x and divide x by 11. Here total operations = x%11 ( this many time decreament ) + 1( for division by 11).
- We may go to multiple of 11 which is larger than x. This can be achieved by just adding (11 – x%11) to x and then divid x by 11. Here total operations = 11 – x%11 ( this many time increment ) + 1( for division by 11).
- With considereing above cases we need to write recursive code to find the min operations.
Step-by-step algorithm:
- First checks if x is already less than or equal to y, in which case it simply returns the difference y – x.
- Then checks if the result for the current x value has already been calculated and stored in the dp array. If so, it returns the pre-calculated result.
- If the result is not pre-calculated, it initializes the res variable with the absolute difference abs(x – y).
- It then considers five possible cases to minimize the number of operations:
- Case 1: Subtract 1 from x and recursively call solve with the updated x value.
- Case 2: Divide x by 5 and add the remainder, then recursively call solve with the updated x value.
- Case 3: Divide x by 5, add the remaining value to reach a multiple of 5, and then subtract 1, then recursively call solve with the updated x value.
- Case 4: Divide x by 11 and add the remainder, then recursively call solve with the updated x value.
- Case 5: Divide x by 11, add the remaining value to reach a multiple of 11, and then subtract 1, then recursively call solve with the updated x value.
- then stores the calculated result in the dp array and returns the res value.
Below is the implementation of the algorithm:
C++
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Create a dynamic programming array to store
// previously calculated results
vector<int> dp;
// Recursive function to calculate the minimum
// operations
int solve(int x, int y)
{
if (x <= y) {
// Base case: if x is already less than or equal
// to y, return the difference
return y - x;
}
if (dp[x] != -1) {
// Memoization: return pre-calculated result if
// available
return dp[x];
}
// Initialize minimum operations with the absolute
// difference
int res = abs(x - y);
// Case 1: Subtract 1 from x
res = min(res, 1 + solve(x - 1, y));
// Case 2: Divide x by 5 and add remainder
// (optimized for 5)
res = min(res, 1 + x % 5 + solve(x / 5, y));
// Case 3: Divide x by 5 and add remaining value to
// reach a multiple of 5 before subtracting 1
// (optimized for 5)
res = min(res,
1 + (5 - x % 5) + solve(x / 5 + 1, y));
// Case 4: Divide x by 11 and add remainder
// (optimized for 11)
res = min(res, 1 + x % 11 + solve(x / 11, y));
// Case 5: Divide x by 11 and add remaining value to
// reach a multiple of 11 before subtracting 1
// (optimized for 11)
res = min(res,
1 + (11 - x % 11) + solve(x / 11 + 1, y));
// Store the calculated result for future use
dp[x] = res;
return res;
// Call the recursive function and return the result
return solve(x, y);
}
int minimumOperationsToMakeEqual(int x, int y)
{
dp.resize(10011, -1);
int minOps = solve(x, y);
return minOps;
}
};
int main()
{
// Input: x = 26, y = 1
int x = 26, y = 1;
Solution obj;
cout << "Minimum operations to make " << x << " and "
<< y << " equal: "
<< obj.minimumOperationsToMakeEqual(x, y) << endl;
return 0;
}
import java.util.Arrays;
class Solution {
// Create an array to store previously calculated
// results
int[] dp;
// Recursive function to calculate the minimum
// operations
int solve(int x, int y)
{
if (x <= y) {
// Base case: if x is already less than or equal
// to y, return the difference
return y - x;
}
if (dp[x] != -1) {
// Memoization: return pre-calculated result if
// available
return dp[x];
}
// Initialize minimum operations with the absolute
// difference
int res = Math.abs(x - y);
// Case 1: Subtract 1 from x
res = Math.min(res, 1 + solve(x - 1, y));
// Case 2: Divide x by 5 and add remainder
// (optimized for 5)
res = Math.min(res, 1 + x % 5 + solve(x / 5, y));
// Case 3: Divide x by 5 and add remaining value to
// reach a multiple of 5 before subtracting 1
// (optimized for 5)
res = Math.min(res, 1 + (5 - x % 5)
+ solve(x / 5 + 1, y));
// Case 4: Divide x by 11 and add remainder
// (optimized for 11)
res = Math.min(res, 1 + x % 11 + solve(x / 11, y));
// Case 5: Divide x by 11 and add remaining value to
// reach a multiple of 11 before subtracting 1
// (optimized for 11)
res = Math.min(res, 1 + (11 - x % 11)
+ solve(x / 11 + 1, y));
// Store the calculated result for future use
dp[x] = res;
return res;
}
int minimumOperationsToMakeEqual(int x, int y)
{
dp = new int[10011];
Arrays.fill(dp, -1);
int minOps = solve(x, y);
return minOps;
}
}
public class Main {
public static void main(String[] args)
{
// Input: x = 26, y = 1
int x = 26, y = 1;
Solution obj = new Solution();
System.out.println(
"Minimum operations to make " + x + " and " + y
+ " equal: "
+ obj.minimumOperationsToMakeEqual(x, y));
}
}
// This code is contributed by Shivam Gupta
class Solution:
def __init__(self):
# Create a dynamic programming array to store previously calculated results
self.dp = [-1] * 10011
# Recursive function to calculate the minimum operations
def solve(self, x, y):
if x <= y:
# Base case: if x is already less than or equal to y, return the difference
return y - x
if self.dp[x] != -1:
# Memoization: return pre-calculated result if available
return self.dp[x]
# Initialize minimum operations with the absolute difference
res = abs(x - y)
# Case 1: Subtract 1 from x
res = min(res, 1 + self.solve(x - 1, y))
# Case 2: Divide x by 5 and add remainder (optimized for 5)
res = min(res, 1 + x % 5 + self.solve(x // 5, y))
# Case 3: Divide x by 5 and add remaining value to reach a multiple of 5
# before subtracting 1 (optimized for 5)
res = min(res, 1 + (5 - x % 5) + self.solve(x // 5 + 1, y))
# Case 4: Divide x by 11 and add remainder (optimized for 11)
res = min(res, 1 + x % 11 + self.solve(x // 11, y))
# Case 5: Divide x by 11 and add remaining value to reach a multiple of 11 before
# subtracting 1 (optimized for 11)
res = min(res, 1 + (11 - x % 11) + self.solve(x // 11 + 1, y))
# Store the calculated result for future use
self.dp[x] = res
return res
def minimumOperationsToMakeEqual(self, x, y):
self.dp = [-1] * 10011
minOps = self.solve(x, y)
return minOps
if __name__ == "__main__":
# Input: x = 26, y = 1
x = 26
y = 1
obj = Solution()
print(f"Minimum operations to make {x} and {y} equal: {obj.minimumOperationsToMakeEqual(x, y)}")
# This code is contributed by Ayush Mishra
OutputMinimum operations to make 26 and 1 equal: 3
Time Complexity: O(N)
Auxiliary Space: O(N)
|
