Given a positive integer N > 1, the task is to find the maximum GCD among all the pairs (i, j) such that i < j < N.
Examples:
Input: N = 3
Output: 3
Explanation:
All the possible pairs are: (1, 2) (1, 3) (2, 3) with GCD 1.
Input: N = 4
Output: 2
Explanation:
Out of all the possible pairs the pair with max GCD is (2, 4) with a value 2.
Naive Approach: Generate all possible pair of integers from the range [1, N] and calculate GCD of all pairs. Finally, print the maximum GCD obtained.
- Initialize a variable maxHcf to INT_MIN to store the maximum GCD found.
- Use nested loops to iterate over all possible pairs (i, j) where i <= j <= n.
- Inside the nested loops, calculate the GCD of the pair (i, j) using the __gcd(i, j) function from the bits/stdc++.h library.
- Update the value of maxHcf to the maximum of its current value and the GCD of the current pair using the max() function.
- After all pairs have been checked, return the value of maxHcf as the maximum GCD of all pairs possible from first n natural numbers.
maxGCD(n):
maxHcf = INT_MIN
for i from 1 to n:
for j from i+1 to n:
gcd = __gcd(i, j)
maxHcf = max(maxHcf, gcd)
return maxHcf
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int maxGCD( int n)
{
int maxHcf = INT_MIN;
for ( int i = 1; i <= n; i++) {
for ( int j = i + 1; j <= n; j++) {
maxHcf
= max(maxHcf, __gcd(i, j));
}
}
return maxHcf;
}
int main()
{
int n = 4;
cout << maxGCD(n);
return 0;
}
|
Java
import java.io.*;
class GFG{
static int maxGCD( int n)
{
int maxHcf = Integer.MIN_VALUE;
for ( int i = 1 ; i <= n; i++)
{
for ( int j = i + 1 ; j <= n; j++)
{
maxHcf = Math.max(maxHcf,
__gcd(i, j));
}
}
return maxHcf;
}
static int __gcd( int a, int b)
{
return b == 0 ? a :
__gcd(b, a % b);
}
public static void main(String[] args)
{
int n = 4 ;
System.out.print(maxGCD(n));
}
}
|
Python3
def __gcd(a, b):
if (b = = 0 ):
return a;
else :
return __gcd(b, a % b);
def maxGCD(n):
maxHcf = - 2391734235435 ;
for i in range ( 1 , n + 1 ):
for j in range (i + 1 , n + 1 ):
maxHcf = max (maxHcf, __gcd(i, j));
return maxHcf;
if __name__ = = '__main__' :
n = 4 ;
print (maxGCD(n));
|
C#
using System;
class GFG{
static int maxGCD( int n)
{
int maxHcf = int .MinValue;
for ( int i = 1; i <= n; i++)
{
for ( int j = i + 1; j <= n; j++)
{
maxHcf = Math.Max(maxHcf,
__gcd(i, j));
}
}
return maxHcf;
}
static int __gcd( int a, int b)
{
return b == 0 ? a :
__gcd(b, a % b);
}
public static void Main(String[] args)
{
int n = 4;
Console.Write(maxGCD(n));
}
}
|
Javascript
<script>
function maxGCD(n) {
var maxHcf = Number.MIN_VALUE;
for (i = 1; i <= n; i++) {
for (j = i + 1; j <= n; j++) {
maxHcf = Math.max(maxHcf, __gcd(i, j));
}
}
return maxHcf;
}
function __gcd(a , b) {
return b == 0 ? a : __gcd(b, a % b);
}
var n = 4;
document.write(maxGCD(n));
</script>
|
Time Complexity: O(N 2 log N)
Auxiliary Space: O(1)
Efficient Approach: The GCD of N and N / 2 is N / 2 which is the maximum of all GCDs possible for any pair from 1 to N.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int maxGCD( int n)
{
return (n / 2);
}
int main()
{
int n = 4;
cout << maxGCD(n);
return 0;
}
|
Java
import java.io.*;
public class GFG{
static int maxGCD( int n)
{
return (n / 2 );
}
public static void main(String[] args)
{
int n = 4 ;
System.out.print(maxGCD(n));
}
}
|
Python3
def maxGCD(n):
return (n / / 2 );
if __name__ = = '__main__' :
n = 4 ;
print (maxGCD(n));
|
C#
using System;
class GFG{
static int maxGCD( int n)
{
return (n / 2);
}
public static void Main(String[] args)
{
int n = 4;
Console.Write(maxGCD(n));
}
}
|
Javascript
<script>
function maxGCD(n)
{
return parseInt(n / 2);
}
var n = 4;
document.write( maxGCD(n));
</script>
|
Time Complexity: O(1)
Auxiliary Space: O(1)