Maximum GCD of two numbers possible by adding same value to them

0 0 2 minutes read

Given two numbers A and B, the task is to find the maximum Greatest Common Divisors(GCD) that can be obtained by adding a number X to both A and B.

Examples

Input: A = 1, B = 5
Output: 4
Explanation: Adding X = 15, the obtained numbers are A = 16 and B = 20. Therefore, GCD of A, B is 4.

Input: A = 2, B = 23
Output: 21

Approach: This problem can be solved in a very optimized manner using the properties of Euclidean GCD algorithm. Follow the steps below to solve the problem:

If a > b: GCD(a, b)= GCD(a – b, b). Therefore, GCD(a, b) = GCD(a – b, b).
On adding x to A, B, gcd(a + x, b + x) = gcd(a – b, b + x). It can be seen that (a – b) remains constant.
It can be safely said that the GCD of these numbers will never exceed (a – b). Since (b + x) can be made a multiple of (a – b) by adding a possible value of x.
Therefore, it can be concluded that GCD remains (a – b).

Below is the implementation of the above approach.

C++

// C++ implementation of above approach.
#include <iostream>
using namespace std;
 
// Function to calculate maximum
// gcd of two numbers possible by
// adding same value to both a and b
void maxGcd(int a, int b)
{
    cout << abs(a - b);
}
 
// Driver Code
int main()
{
    // Given Input
    int a = 2231;
    int b = 343;
 
    maxGcd(a, b);
 
    return 0;
}

Java

// Java implementation of above approach.
import java.io.*;
 
class GFG 
{
 
  // Function to calculate maximum
  // gcd of two numbers possible by
  // adding same value to both a and b
  static void maxGcd(int a, int b)
  {
    System.out.println(Math.abs(a - b));
  }
 
  // Driver Code
  public static void main (String[] args)
  {
 
    // Given Input
    int a = 2231;
    int b = 343;
 
    maxGcd(a, b);
 
  }
}
 
// This code is contributed by Potta Lokesh

Python3

# Python3 program for the above approach
 
# Function to calculate maximum
# gcd of two numbers possible by
# adding same value to both a and b
def maxGcd(a, b):
     
    print(abs(a - b))
 
# Driver code
 
# Given Input
a = 2231
b = 343
 
maxGcd(a, b)
 
# This code is contributed by Parth Manchanda

C#

// C# program for the above approach
using System;
 
class GFG{
 
 // Function to calculate maximum
  // gcd of two numbers possible by
  // adding same value to both a and b
  static void maxGcd(int a, int b)
  {
    Console.Write(Math.Abs(a - b));
  }
 
// Driver Code
static public void Main ()
{
     
     // Given Input
    int a = 2231;
    int b = 343;
 
    maxGcd(a, b);
}
}
 
// This code is contributed by code_hunt.

Javascript

<script>
       // JavaScript Program for the above approach
 
       // Function to calculate maximum
       // gcd of two numbers possible by
       // adding same value to both a and b
       function maxGcd(a, b) {
           document.write(Math.abs(a - b));
       }
 
       // Driver Code
 
       // Given Input
       let a = 2231;
       let b = 343;
 
       maxGcd(a, b);
 
   // This code is contributed by Potta Lokesh
   </script>

Output:

Time Complexity: O(1)
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 zambiatek!