Given two integers X and Y, the task is to make both the integers equal by performing the following operations any number of times:
- Increase X by M times. Cost = M – 1.
- Increase Y by N times. Cost = N – 1.
Examples:
Input: X = 2, Y = 4
Output: 1
Explanation:
Increase X by 2 times. Therefore, X = 2 * 2 = 4. Cost = 1.
Clearly, X = Y. Therefore, total cost = 1.Input: X = 4, Y = 6
Output: 3
Explanation:
Increase X by 3 times, X = 3 * 4 = 12. Cost = 2.
increase Y by 2 times, Y = 2 * 6 = 12. Cost = 1.
Clearly, X = Y. Therefore, total cost = 2 + 1 = 3.
Naive Approach: Follow the steps below to solve the problem:
- For each value of X, if Y is less than X, then increment Y and update cost.
- If X = Y, then print the total cost.
- If X < Y, then increment X and update cost.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <iostream>using namespace std;// Function to find minimum cost// to make x and y equalint minimumCost(int x, int y){ int costx = 0, dup_x = x; while (true) { int costy = 0, dup_y = y; // Check if it possible // to make x == y while (dup_y != dup_x && dup_y < dup_x) { dup_y += y; costy++; } // If both are equal if (dup_x == dup_y) return costx + costy; // Otherwise else { // Increment cost of x // by 1 and dup_x by x dup_x += x; costx++; } }}// Driver Codeint main(){ int x = 5, y = 17; // Returns the required minimum cost cout << minimumCost(x, y) << endl;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find minimum cost// to make x and y equalstatic int minimumCost(int x, int y){ int costx = 0, dup_x = x; while (true) { int costy = 0, dup_y = y; // Check if it possible // to make x == y while (dup_y != dup_x && dup_y < dup_x) { dup_y += y; costy++; } // If both are equal if (dup_x == dup_y) return costx + costy; // Otherwise else { // Increment cost of x // by 1 and dup_x by x dup_x += x; costx++; } }}// Driver Codepublic static void main(String[] args){ int x = 5, y = 17; // Returns the required minimum cost System.out.print(minimumCost(x, y) +"\n");}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach# Function to find minimum cost# to make x and y equaldef minimumCost(x, y): costx, dup_x = 0, x while (True): costy, dup_y = 0, y # Check if it possible # to make x == y while (dup_y != dup_x and dup_y < dup_x): dup_y += y costy += 1 # If both are equal if (dup_x == dup_y): return costx + costy # Otherwise else: # Increment cost of x # by 1 and dup_x by x dup_x += x costx += 1# Driver Codeif __name__ == '__main__': x, y = 5, 17 # Returns the required minimum cost print(minimumCost(x, y))# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG{ // Function to find minimum cost // to make x and y equal static int minimumCost(int x, int y) { int costx = 0, dup_x = x; while (true) { int costy = 0, dup_y = y; // Check if it possible // to make x == y while (dup_y != dup_x && dup_y < dup_x) { dup_y += y; costy++; } // If both are equal if (dup_x == dup_y) return costx + costy; // Otherwise else { // Increment cost of x // by 1 and dup_x by x dup_x += x; costx++; } } } // Driver Code public static void Main(String[] args) { int x = 5, y = 17; // Returns the required minimum cost Console.Write(minimumCost(x, y) +"\n"); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// javascript program for the above approach // Function to find minimum cost // to make x and y equal function minimumCost(x, y) { var costx = 0, dup_x = x; while (true) { var costy = 0, dup_y = y; // Check if it possible // to make x == y while (dup_y != dup_x && dup_y < dup_x) { dup_y += y; costy++; } // If both are equal if (dup_x == dup_y) return costx + costy; // Otherwise else { // Increment cost of x // by 1 and dup_x by x dup_x += x; costx++; } } } // Driver Code var x = 5, y = 17; // Returns the required minimum cost document.write(minimumCost(x, y) + "\n");// This code is contributed by Rajput-Ji </script> |
Output:
20
Time Complexity: O((costx + costy)*Y)
Auxiliary Space: O(1)
Efficient Method: The idea here is to use the concept of LCM. The minimum cost of making both X and Y will be equal to their LCM. But this is not enough. Subtract initial values of X and Y to avoid adding them while calculating answers.
Follow the steps below to solve the problem:
- Find LCM of both X and Y.
- Subtract the value of X and Y from LCM.
- Now, divide the LCM by both X and Y, and the sum of their values is the required answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <iostream>using namespace std;// Function to find gcd of x and yint gcd(int x, int y){ if (y == 0) return x; return gcd(y, x % y);}// Function to find lcm of x and yint lcm(int x, int y){ return (x * y) / gcd(x, y);}// Function to find minimum Costint minimumCost(int x, int y){ int lcm_ = lcm(x, y); // Subtracted initial cost of x int costx = (lcm_ - x) / x; // Subtracted initial cost of y int costy = (lcm_ - y) / y; return costx + costy;}// Driver Codeint main(){ int x = 5, y = 17; // Returns the minimum cost required cout << minimumCost(x, y) << endl;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find gcd of x and ystatic int gcd(int x, int y){ if (y == 0) return x; return gcd(y, x % y);}// Function to find lcm of x and ystatic int lcm(int x, int y){ return (x * y) / gcd(x, y);}// Function to find minimum Coststatic int minimumCost(int x, int y){ int lcm_ = lcm(x, y); // Subtracted initial cost of x int costx = (lcm_ - x) / x; // Subtracted initial cost of y int costy = (lcm_ - y) / y; return costx + costy;}// Driver Codepublic static void main(String[] args){ int x = 5, y = 17; // Returns the minimum cost required System.out.print(minimumCost(x, y) +"\n");}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approach# Function to find gcd of x and ydef gcd(x, y): if (y == 0): return x return gcd(y, x % y)# Function to find lcm of x and ydef lcm(x, y): return (x * y) // gcd(x, y)# Function to find minimum Costdef minimumCost(x, y): lcm_ = lcm(x, y) # Subtracted initial cost of x costx = (lcm_ - x) // x # Subtracted initial cost of y costy = (lcm_ - y) // y return costx + costy# Driver Codeif __name__ == "__main__": x = 5 y = 17 # Returns the minimum cost required print(minimumCost(x, y))# This code is contributed by chitranayal |
C#
// C# program for the above approachusing System;class GFG{// Function to find gcd of x and ystatic int gcd(int x, int y){ if (y == 0) return x; return gcd(y, x % y);}// Function to find lcm of x and ystatic int lcm(int x, int y){ return (x * y) / gcd(x, y);}// Function to find minimum Coststatic int minimumCost(int x, int y){ int lcm_ = lcm(x, y); // Subtracted initial cost of x int costx = (lcm_ - x) / x; // Subtracted initial cost of y int costy = (lcm_ - y) / y; return costx + costy;}// Driver Codepublic static void Main(String[] args){ int x = 5, y = 17; // Returns the minimum cost required Console.Write(minimumCost(x, y) +"\n");}}// This code is contributed by 29AjayKumar |
Javascript
<script>// javascript program for the above approach // Function to find gcd of x and y function gcd(x , y) { if (y == 0) return x; return gcd(y, x % y); } // Function to find lcm of x and y function lcm(x , y) { return (x * y) / gcd(x, y); } // Function to find minimum Cost function minimumCost(x , y) { var lcm_ = lcm(x, y); // Subtracted initial cost of x var costx = (lcm_ - x) / x; // Subtracted initial cost of y var costy = (lcm_ - y) / y; return costx + costy; } // Driver Code var x = 5, y = 17; // Returns the minimum cost required document.write(minimumCost(x, y) + "\n");// This code contributed by gauravrajput1</script> |
Output:
20
Time Complexity: O(log(min(x, y))
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
