Minimum number to be added to minimize LCM of two given numbers

0 0 8 minutes read

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 number
vector<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 minimized
int 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 Code
int main()
{
    // Given A & B
    int A = 6, B = 10;
 
    // Function Call
    findTheSmallestX(A, B);
 
    return 0;
}

Java

// Java program for the 
// above approach
import 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 number
static 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 minimized
static 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 Code
public 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 approach
from math import gcd
 
# Function for finding all divisors
# of a given number
def 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 minimized
def 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 Code
if __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 approach
using 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 number
static 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 minimized
static 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 Code
public 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 number
function 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 minimized
function 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 & B
let A = 6, B = 10;
 
// Function Call
findTheSmallestX(A, B);
 
 
// This code is contributed by patel2127
 
</script>

Output:

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 zambiatek!