Find the maximum GCD possible for some pair in a given range [L, R]

0 0 4 minutes read

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)²Log(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 GCD
int GCD(int a, int b)
{
    if (b == 0)
        return a;
    return GCD(b, a % b);
}
 
// Function to calculate
// maximum GCD in a range
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
int main()
{
    // Input
    int L = 102;
    int R = 139;
 
    // Function Call
    cout << maxGCDInRange(L, R);
 
    return 0;
}

Java

// Java program for the above approach
import 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 GCD
def GCD(a, b):
     
    if (b == 0):
        return a
         
    return GCD(b, a % b)
 
# Function to calculate
# maximum GCD in a range
def 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
 
# Input
L = 102
R = 139
 
# Function Call
print(maxGCDInRange(L, R))
 
# This code is contributed by SoumikMondal

C#

// C# program for the above approach
using System;
 
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()
{
     
    // 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 GCD
function GCD( a, b)
{
    if (b == 0)
        return a;
    return GCD(b, a % b);
}
 
// Function to calculate
// maximum GCD in a range
function 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
 
// Input
let L = 102;
let R = 139;
 
// Function Call
document.write(maxGCDInRange(L, R));
 
// This code is contributed by Potta Lokesh
 
</script>

Output

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