Given a range L to R, the task is to find the maximum possible value of GCD(X, Y) such that X and Y belongs to the given range, i.e. L ? X < Y ? R.
Examples:
Input: L = 101, R = 139
Output:
34
Explanation:
For X = 102 and Y = 136, the GCD of x and y is 34, which is the maximum possible.Input: L = 8, R = 14
Output:
7Â
Naive Approach: Every pair that can be formed from L to R, can be iterated over using two nested loops and the maximum GCD can be found.
Time Complexity: O((R-L)2Log(R))
Auxiliary Space: O(1)
Efficient Approach: Follow the below steps to solve the problem:
- Let the maximum GCD be Z, therefore, X and Y are both multiples of Z. Conversely if there are two or more multiples of Z in the segment [L, R], then (X, Y) can be chosen such that GCD(x, y) is maximum by choosing consecutive multiples of Z in [L, R].
- Iterate from R to 1 and find whether any of them has at least two multiples in the range [L, R]
- The multiples of Z between L and R can be calculated using the following formula:
- Number of Multiples of Z in [L, R] = Number of multiples of Z in [1, R] – Number of Multiples of Z in [1, L-1]
- This can be written as :
- No. of Multiples of Z in [L, R] = floor(R/Z) – floor((L-1)/Z)
- We can further optimize this by limiting the iteration from R/2 to 1 as the greatest possible GCD is R/2 (with multiples R/2 and R)
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;Â
// Function to calculate GCDint GCD(int a, int b){Â Â Â Â if (b == 0)Â Â Â Â Â Â Â Â return a;Â Â Â Â return GCD(b, a % b);}Â
// Function to calculate// maximum GCD in a rangeint maxGCDInRange(int L, int R){    // Variable to store the answer    int ans = 1;Â
    for (int Z = R/2; Z >= 1; Z--) {Â
        // If Z has two multiples in [L, R]        if ((R / Z) - ((L - 1) / Z) > 1) {Â
            // Update ans            ans = Z;            break;        }    }Â
    // Return the value    return ans;}// Driver codeint main(){    // Input    int L = 102;    int R = 139;Â
    // Function Call    cout << maxGCDInRange(L, R);Â
    return 0;} |
Java
// Java program for the above approachimport java.io.*;Â
class GFG {Â Â Â Â // Function to calculate GCDÂ Â Â Â public static int GCD(int a, int b)Â Â Â Â {Â Â Â Â Â Â Â Â if (b == 0)Â Â Â Â Â Â Â Â Â Â Â Â return a;Â Â Â Â Â Â Â Â return GCD(b, a % b);Â Â Â Â }Â
    // Function to calculate    // maximum GCD in a range    public static int maxGCDInRange(int L, int R)    {        // Variable to store the answer        int ans = 1;Â
        for (int Z = R/2; Z >= 1; Z--) {Â
            // If Z has two multiples in [L, R]            if ((R / Z) - ((L - 1) / Z) > 1) {Â
                // Update ans                ans = Z;                break;            }        }Â
        // Return the value        return ans;    }     // Driver code    public static void main(String[] args)    {        // Input        int L = 102;        int R = 139;Â
        // Function Call        System.out.println(maxGCDInRange(L, R));    }Â
      // This code is contributed by Potta Lokesh |
Python3
# Python3 program for the above approachÂ
# Function to calculate GCDdef GCD(a, b):         if (b == 0):        return a             return GCD(b, a % b)Â
# Function to calculate# maximum GCD in a rangedef maxGCDInRange(L, R):         # Variable to store the answer    ans = 1Â
    for Z in range(R//2, 1, -1):                 # If Z has two multiples in [L, R]        if (((R // Z) - ((L - 1) // Z )) > 1):                         # Update ans            ans = Z            break             # Return the value    return ansÂ
# Driver codeÂ
# InputL = 102R = 139Â
# Function Callprint(maxGCDInRange(L, R))Â
# This code is contributed by SoumikMondal |
C#
// C# program for the above approachusing System;Â
class GFG{Â Â Â Â Â // Function to calculate GCDpublic static int GCD(int a, int b){Â Â Â Â if (b == 0)Â Â Â Â Â Â Â Â return a;Â Â Â Â Â Â Â Â Â Â Â Â Â return GCD(b, a % b);}Â
// Function to calculate// maximum GCD in a rangepublic static int maxGCDInRange(int L, int R){         // Variable to store the answer    int ans = 1;Â
    for(int Z = R/2; Z >= 1; Z--)    {                 // If Z has two multiples in [L, R]        if ((R / Z) - ((L - 1) / Z) > 1)        {                         // Update ans            ans = Z;            break;        }    }Â
    // Return the value    return ans;}Â
// Driver codepublic static void Main(){         // Input    int L = 102;    int R = 139;Â
    // Function Call    Console.Write(maxGCDInRange(L, R));}}Â
// This code is contributed by rishavmahato348 |
Javascript
<script>Â
// JavaScript program for the above approachÂ
// Function to calculate GCDfunction GCD( a, b){Â Â Â Â if (b == 0)Â Â Â Â Â Â Â Â return a;Â Â Â Â return GCD(b, a % b);}Â
// Function to calculate// maximum GCD in a rangefunction maxGCDInRange(L, R){Â
    // Variable to store the answer    let ans = 1;Â
    for (let Z = parseInt((R / 2)); Z >= 1; Z--)     {             // If Z has two multiples in [L, R]        if (parseInt((R / Z)) - parseInt((L - 1) / Z ) > 1)         {                     // Update ans            ans = Z;            break;        }    }Â
    // Return the value    return ans;}Â
// Driver codeÂ
// Inputlet L = 102;let R = 139;Â
// Function Calldocument.write(maxGCDInRange(L, R));Â
// This code is contributed by Potta LokeshÂ
</script> |
Output
34
Time Complexity: O(R)
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!
… [Trackback]
[…] Read More on that Topic: geeksforgeeks.org/find-the-maximum-gcd-possible-for-some-pair-in-a-given-range-l-r/ […]