Given two numbers A and B, the task is to find the minimum number that needs to be added to A and B such that their LCM is minimized.
Examples:
Input: A = 6, B = 10
Output: 2
Explanation: On adding 2 to A and B, the value becomes 8 and 12 respectively. LCM of 8 and 12 is 24, which is the minimum LCM possible.Input: A = 5, B = 10
Output: 0
Explanation:
10 is already the minimum LCM of both the given number.
Hence, the minimum number added is 0.
Approach: The idea is based on the generalized formula that the LCM of (A + x) and (B + x) is equal to (A + x)*(B + x) / GCD(A + x, B + x). It can be observed that GCD of (A + x) and (B + x) is is equal to the GCD of (B – A) and (A + x). So, the gcd is a divisor of (B ? A).
Therefore, iterate over all the divisors of (B ? A) and if A % M = B % M (if M is one of the divisors), then the value of X(the minimum value must be added) is equal to M ? A % M.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include "bits/stdc++.h"using namespace std;// Function for finding all divisors// of a given numbervector<int> getDivisors(int diff){ // Stores the divisors of the // number diff vector<int> divisor; for (int i = 1; i * i <= diff; i++) { // If diff is a perfect square if (i == diff / i) { divisor.push_back(i); continue; } // If i divides diff then // diff / i also a divisor if (diff % i == 0) { divisor.push_back(i); divisor.push_back(diff / i); } } // Return the divisors stored return divisor;}// Function to find smallest integer x// such that LCM of (A + X) and (B + X)// is minimizedint findTheSmallestX(int a, int b){ int diff = b - a; // Find all the divisors of diff vector<int> divisor = getDivisors(diff); // Find LCM of a and b int lcm = (a * b) / __gcd(a, b); int ans = 0; for (int i = 0; i < (int)divisor.size(); i++) { // From equation x = M - a % M // here M = divisor[i] int x = (divisor[i] - (a % divisor[i])); // If already checked for x == 0 if (!x) continue; // Find the product int product = (b + x) * (a + x); // Find the GCD int tempGCD = __gcd(a + x, b + x); int tempLCM = product / tempGCD; // If current lcm is minimum // than previous lcm, update ans if (lcm > tempLCM) { ans = x; lcm = tempLCM; } } // Print the number added cout << ans;}// Driver Codeint main(){ // Given A & B int A = 6, B = 10; // Function Call findTheSmallestX(A, B); return 0;} |
Java
// Java program for the // above approachimport java.util.*;class GFG{ // Recursive function to // return gcd of a and b static int __gcd(int a, int b) { return b == 0 ? a : __gcd(b, a % b); } // Function for finding all // divisors of a given numberstatic int[] getDivisors(int diff){ // Stores the divisors of // the number diff Vector<Integer> divisor = new Vector<>() ; for (int i = 1; i * i <= diff; i++) { // If diff is a perfect // square if (i == diff / i) { divisor.add(i); continue; } // If i divides diff then // diff / i also a divisor if (diff % i == 0) { divisor.add(i); divisor.add(diff / i); } } int []ans = new int[divisor.size()]; int j = 0; for(int i: divisor) ans[j] = i; // Return the divisors // stored return ans;}// Function to find smallest integer // x such that LCM of (A + X) and // (B + X) is minimizedstatic void findTheSmallestX(int a, int b){ int diff = b - a; // Find all the divisors // of diff int[] divisor = getDivisors(diff); // Find LCM of a and b int lcm = (a * b) / __gcd(a, b); int ans = 0; for (int i = 0; i <divisor.length; i++) { // From equation x = M - a % M // here M = divisor[i] int x = 0; if(divisor[i] != 0) x = (divisor[i] - (a % divisor[i])); // If already checked for // x == 0 if (x == 0) continue; // Find the product int product = (b + x) * (a + x); // Find the GCD int tempGCD = __gcd(a + x, b + x); int tempLCM = product / tempGCD; // If current lcm is // minimum than previous // lcm, update ans if (lcm > tempLCM) { ans = x; lcm = tempLCM; } } // Print the number // added System.out.print(ans);}// Driver Codepublic static void main(String[] args){ // Given A & B int A = 6, B = 10; // Function Call findTheSmallestX(A, B);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approachfrom math import gcd# Function for finding all divisors# of a given numberdef getDivisors(diff): # Stores the divisors of the # number diff divisor = [] for i in range(1, diff): if i * i > diff: break # If diff is a perfect square if (i == diff // i): divisor.append(i) continue # If i divides diff then # diff / i also a divisor if (diff % i == 0): divisor.append(i) divisor.append(diff // i) # Return the divisors stored return divisor# Function to find smallest integer x# such that LCM of (A + X) and (B + X)# is minimizeddef findTheSmallestX(a, b): diff = b - a # Find all the divisors of diff divisor = getDivisors(diff) # Find LCM of a and b lcm = (a * b) // gcd(a, b) ans = 0 for i in range(len(divisor)): # From equation x = M - a % M # here M = divisor[i] x = (divisor[i] - (a % divisor[i])) # If already checked for x == 0 if (not x): continue # Find the product product = (b + x) * (a + x) # Find the GCD tempGCD = gcd(a + x, b + x) tempLCM = product // tempGCD # If current lcm is minimum # than previous lcm, update ans if (lcm > tempLCM): ans = x lcm = tempLCM # Print the number added print(ans)# Driver Codeif __name__ == '__main__': # Given A & B A = 6 B = 10 # Function Call findTheSmallestX(A, B)# This code is contributed by mohit kumar 29 |
C#
// C# program for the // above approachusing System;using System.Collections.Generic;class GFG{ // Recursive function to // return gcd of a and b static int __gcd(int a, int b) { return b == 0 ? a : __gcd(b, a % b); } // Function for finding all // divisors of a given numberstatic int[] getDivisors(int diff){ // Stores the divisors of // the number diff List<int> divisor = new List<int>(); for(int i = 1; i * i <= diff; i++) { // If diff is a perfect // square if (i == diff / i) { divisor.Add(i); continue; } // If i divides diff then // diff / i also a divisor if (diff % i == 0) { divisor.Add(i); divisor.Add(diff / i); } } int []ans = new int[divisor.Count]; int j = 0; foreach(int i in divisor) ans[j] = i; // Return the divisors // stored return ans;}// Function to find smallest integer // x such that LCM of (A + X) and // (B + X) is minimizedstatic void findTheSmallestX(int a, int b){ int diff = b - a; // Find all the divisors // of diff int[] divisor = getDivisors(diff); // Find LCM of a and b int lcm = (a * b) / __gcd(a, b); int ans = 0; for(int i = 0; i < divisor.Length; i++) { // From equation x = M - a % M // here M = divisor[i] int x = 0; if (divisor[i] != 0) x = (divisor[i] - (a % divisor[i])); // If already checked for // x == 0 if (x == 0) continue; // Find the product int product = (b + x) * (a + x); // Find the GCD int tempGCD = __gcd(a + x, b + x); int tempLCM = product / tempGCD; // If current lcm is // minimum than previous // lcm, update ans if (lcm > tempLCM) { ans = x; lcm = tempLCM; } } // Print the number // added Console.Write(ans);}// Driver Codepublic static void Main(String[] args){ // Given A & B int A = 6, B = 10; // Function Call findTheSmallestX(A, B);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript program for the// above approach// Recursive function to// return gcd of a and b function __gcd(a,b){ return b == 0 ? a : __gcd(b, a % b); }// Function for finding all// divisors of a given numberfunction getDivisors(diff){ // Stores the divisors of // the number diff let divisor = []; for (let i = 1; i * i <= diff; i++) { // If diff is a perfect // square if (i == diff / i) { divisor.push(i); continue; } // If i divides diff then // diff / i also a divisor if (diff % i == 0) { divisor.push(i); divisor.push(diff / i); } } let ans = new Array(divisor.length); let j = 0; for(let i=0;i< divisor.length;i++) ans[i] = divisor[i]; // Return the divisors // stored return ans;}// Function to find smallest integer// x such that LCM of (A + X) and// (B + X) is minimizedfunction findTheSmallestX(a,b){ let diff = b - a; // Find all the divisors // of diff let divisor = getDivisors(diff); // Find LCM of a and b let lcm = (a * b) / __gcd(a, b); let ans = 0; for (let i = 0; i <divisor.length; i++) { // From equation x = M - a % M // here M = divisor[i] let x = 0; if(divisor[i] != 0) x = (divisor[i] - (a % divisor[i])); // If already checked for // x == 0 if (x == 0) continue; // Find the product let product = (b + x) * (a + x); // Find the GCD let tempGCD = __gcd(a + x, b + x); let tempLCM = product / tempGCD; // If current lcm is // minimum than previous // lcm, update ans if (lcm > tempLCM) { ans = x; lcm = tempLCM; } } // Print the number // added document.write(ans);}// Driver Code// Given A & Blet A = 6, B = 10;// Function CallfindTheSmallestX(A, B);// This code is contributed by patel2127</script> |
Output:
2
Time Complexity: O(sqrt(B – A))
Auxiliary Space: O(max(A, B))
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!
