# Minimize cost to make X and Y equal by given increments

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:**

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

Input:X = 2, Y = 4Output:1Explanation:

Increase X by 2 times. Therefore, X = 2 * 2 = 4. Cost = 1.

Clearly, X = Y. Therefore, total cost = 1.

Input:X = 4, Y = 6Output:3Explanation:

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 equal` `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++;` ` ` `}` ` ` `// Iif 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` `int` `main()` `{` ` ` `int` `x = 5, y = 17;` ` ` `// Returns the required minimum cost` ` ` `cout << minimumCost(x, y) << endl;` `}` |

## Java

`// Java program for the above approach` `import` `java.util.*;` `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++;` ` ` `}` ` ` `// Iif 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` ` ` `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 equal` `def` `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 Code` `if` `__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 approach` `using` `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++;` ` ` `}` ` ` `// Iif 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++;` ` ` `}` ` ` `// Iif 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 y` `int` `gcd(` `int` `x, ` `int` `y)` `{` ` ` `if` `(y == 0)` ` ` `return` `x;` ` ` `return` `gcd(y, x % y);` `}` `// Function to find lcm of x and y` `int` `lcm(` `int` `x, ` `int` `y)` `{` ` ` `return` `(x * y) / gcd(x, y);` `}` `// Function to find minimum Cost` `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 Code` `int` `main()` `{` ` ` `int` `x = 5, y = 17;` ` ` `// Returns the minimum cost required` ` ` `cout << minimumCost(x, y) << endl;` `}` |

## Java

`// Java program for the above approach` `import` `java.util.*;` `class` `GFG` `{` `// Function to find gcd of x and y` `static` `int` `gcd(` `int` `x, ` `int` `y)` `{` ` ` `if` `(y == ` `0` `)` ` ` `return` `x;` ` ` `return` `gcd(y, x % y);` `}` `// Function to find lcm of x and y` `static` `int` `lcm(` `int` `x, ` `int` `y)` `{` ` ` `return` `(x * y) / gcd(x, y);` `}` `// Function to find minimum Cost` `static` `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 Code` `public` `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 y` `def` `gcd(x, y):` ` ` ` ` `if` `(y ` `=` `=` `0` `):` ` ` `return` `x` ` ` ` ` `return` `gcd(y, x ` `%` `y)` `# Function to find lcm of x and y` `def` `lcm(x, y):` ` ` `return` `(x ` `*` `y) ` `/` `/` `gcd(x, y)` `# Function to find minimum Cost` `def` `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 Code` `if` `__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 approach` `using` `System;` `class` `GFG` `{` `// Function to find gcd of x and y` `static` `int` `gcd(` `int` `x, ` `int` `y)` `{` ` ` `if` `(y == 0)` ` ` `return` `x;` ` ` `return` `gcd(y, x % y);` `}` `// Function to find lcm of x and y` `static` `int` `lcm(` `int` `x, ` `int` `y)` `{` ` ` `return` `(x * y) / gcd(x, y);` `}` `// Function to find minimum Cost` `static` `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 Code` `public` `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)