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 bvoid maxGcd(int a, int b){ cout << abs(a - b);}// Driver Codeint 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 bdef maxGcd(a, b): print(abs(a - b))# Driver code# Given Inputa = 2231b = 343maxGcd(a, b)# This code is contributed by Parth Manchanda |
C#
// C# program for the above approachusing 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 Codestatic 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:
1888
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
