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!
