Given two integers L and R, where L < R, the task is to find Co-prime numbers X and Y such that L <= X < Y <= R and the difference between X and Y is maximum i.e., maximize (Y – X) over all pairs between L and R where GCD(X, Y) = 1.
Note: Co-prime numbers are the numbers whose GCD (Greatest Common Divisor) is 1 i.e., A and B are Co-prime if and only if GCD(A, B) = 1.
Examples:
Input: L = 3, R = 9
Output: 5
Explanation: {3, 8}, and {4, 9} are both Co-prime number in the range [3, 9] with a maximum difference of 5. So the answer is 5.Input: L = 4, R =5
Output: 1
Explanation: Only one pair {4, 5} is possible in the given range, so the maximum difference is 1.
Naive Approach: Follow the steps to solve the problem:
- Initialize a variable maxDifference = 0 to store the maximum difference as the answer.
- Run a loop on i from L to R – 1 and inside that loop perform the below steps
- Run a nested loop on j from i + 1 to R
- If GCD(i, j) == 1 update maxDifference = max(maxDifference, j – i ).
- Return maxDifference as the final answer.
Time complexity: O((R – L)^2)*log(R)), (R- L)^2 for nested loops and log(R) for calculating GCD(L, R) over all pairs.
Auxiliary Space: O(1)
Efficient Approach: To solve the problem use the following idea:
As we know that GCD(N, N + 1) is always 1 and we need to find the maximum difference of the pair with GCD 1 so GCD(L, R – 1) and GCD(L + 1, R) will be one as GCD(L, L + 1) and GCD(R – 1, R) will be 1 so there cannot be any common factors between (L and R – 1), and (L + 1, R).
Follow the below steps to solve the problem:
- If the GCD(L, R) = 1
- Return (R – L) as the answer.
- else return (R – L – 1) as the answer.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to calculate the// gcd of a and bint gcd(int a, int b){ if (a == 0) return b; return gcd(b % a, a);}// function to find the maximum differenceint maxDifference(int l, int r){ // if the GCD of L and R is 1 // R - L is maximum difference if (gcd(l, r) == 1) { return (r - l); } // GCD(L + 1, R) or GCD(L, R - 1) // will always be 1 as N and N + 1 // are co-primes return (r - l - 1);}// Driver codeint main(){ // Range for which we want to // calculate maximum difference int L = 3, R = 9; // Function Call cout << maxDifference(L, R); return 0;} |
Java
// Java code for the above approachimport java.io.*;class GFG { // Driver Code public static void main(String[] args) { // Range for which we want to calculate maximum difference // input int L = 3, R = 9; // Function Call int answer = maxDifference(L, R); // Printing the answer System.out.println(answer); } static // function to find the maximum difference int maxDifference(int l, int r) { // if the GCD of L and R is 1 // R - L is maximum difference if (gcd(l, r) == 1) { return (r - l); } // GCD(L + 1, R) or GCD(L, R - 1) // will always be 1 as N and N + 1 // are co-primes return (r - l - 1); } // Function to calculate the gcd of a and b static int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a); }} |
Python3
# Python code for the above approach# function to find the maximum differencedef maxDifference(l, r): # if the GCD of L and R is 1 # R - L is maximum difference if (gcd(l, r) == 1): return (r - l) # GCD(L + 1, R) or GCD(L, R - 1) # will always be 1 as N and N + 1 # are co-primes return (r - l - 1)# Function to calculate the gcd of a and bdef gcd(a, b): if (a == 0): return b return gcd(b % a, a)# Driver Code# Range for which we want to calculate maximum difference# inputL = 3R = 9# Function Callanswer = maxDifference(L, R)# Printing the answerprint(answer)# This code is contributed by saurabh_jaiswal. |
C#
// C# program for above approachusing System;using System.Linq;class GFG{ // function to find the maximum difference static int maxDifference(int l, int r) { // if the GCD of L and R is 1 // R - L is maximum difference if (gcd(l, r) == 1) { return (r - l); } // GCD(L + 1, R) or GCD(L, R - 1) // will always be 1 as N and N + 1 // are co-primes return (r - l - 1); } // Function to calculate the gcd of a and b static int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a); }// Driver Codepublic static void Main(){ // Range for which we want to calculate maximum difference // input int L = 3, R = 9; // Function Call int answer = maxDifference(L, R); // Printing the answer Console.Write(answer);}}// This code is contributed by code_hunt. |
Javascript
<script>// JavaScript code for the above approach // function to find the maximum difference function maxDifference(l, r) { // if the GCD of L and R is 1 // R - L is maximum difference if (gcd(l, r) == 1) { return (r - l); } // GCD(L + 1, R) or GCD(L, R - 1) // will always be 1 as N and N + 1 // are co-primes return (r - l - 1); } // Function to calculate the gcd of a and b function gcd(a, b) { if (a == 0) return b; return gcd(b % a, a); }// Driver Code // Range for which we want to calculate maximum difference // input let L = 3, R = 9; // Function Call let answer = maxDifference(L, R); // Printing the answer document.write(answer); </script> |
5
Time complexity: O(log(L)), for calculating GCD(L, R)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
