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.
Algorithm:
- 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.
PseudoCode:
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++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find maximum gcd// of all pairs possible from// first n natural numbersint maxGCD(int n){ // Stores maximum gcd int maxHcf = INT_MIN; // Iterate over all possible pairs for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { // Update maximum GCD maxHcf = max(maxHcf, __gcd(i, j)); } } return maxHcf;}// Driver Codeint main(){ int n = 4; cout << maxGCD(n); return 0;} |
Java
// Java program for // the above approachimport java.io.*;class GFG{// Function to find maximum gcd// of all pairs possible from// first n natural numbersstatic int maxGCD(int n){ // Stores maximum gcd int maxHcf = Integer.MIN_VALUE; // Iterate over all possible pairs for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { // Update maximum GCD maxHcf = Math.max(maxHcf, __gcd(i, j)); } } return maxHcf;} static int __gcd(int a, int b) { return b == 0 ? a : __gcd(b, a % b); } // Driver Codepublic static void main(String[] args){ int n = 4; System.out.print(maxGCD(n));}}// This code is contributed by Rajput-Ji |
Python3
# Python3 program for # the above approachdef __gcd(a, b): if(b == 0): return a; else: return __gcd(b, a % b);# Function to find maximum gcd# of all pairs possible from# first n natural numbersdef maxGCD(n): # Stores maximum gcd maxHcf = -2391734235435; # Iterate over all possible pairs for i in range(1, n + 1): for j in range(i + 1, n + 1): # Update maximum GCD maxHcf = max(maxHcf, __gcd(i, j)); return maxHcf;# Driver Codeif __name__ == '__main__': n = 4; print(maxGCD(n));# This code is contributed by gauravrajput1 |
C#
// C# program for // the above approachusing System;class GFG{// Function to find maximum gcd// of all pairs possible from// first n natural numbersstatic int maxGCD(int n){ // Stores maximum gcd int maxHcf = int.MinValue; // Iterate over all possible pairs for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { // Update maximum GCD maxHcf = Math.Max(maxHcf, __gcd(i, j)); } } return maxHcf;} static int __gcd(int a, int b) { return b == 0 ? a : __gcd(b, a % b); } // Driver Codepublic static void Main(String[] args){ int n = 4; Console.Write(maxGCD(n));}}// This code is contributed by 29AjayKumar |
Javascript
<script>// javascript program for // the above approach // Function to find maximum gcd // of all pairs possible from // first n natural numbers function maxGCD(n) { // Stores maximum gcd var maxHcf = Number.MIN_VALUE; // Iterate over all possible pairs for (i = 1; i <= n; i++) { for (j = i + 1; j <= n; j++) { // Update maximum GCD maxHcf = Math.max(maxHcf, __gcd(i, j)); } } return maxHcf; } function __gcd(a , b) { return b == 0 ? a : __gcd(b, a % b); } // Driver Code var n = 4; document.write(maxGCD(n));// This code contributed by umadevi9616 </script> |
Output:
2
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++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum GCD// among all the pairs from// first n natural numbersint maxGCD(int n){ // Return max GCD return (n / 2);}// Driver Codeint main(){ int n = 4; cout << maxGCD(n); return 0;} |
Java
// Java implementation of the above approachimport java.io.*;public class GFG{ // Function to find the maximum GCD// among all the pairs from// first n natural numbersstatic int maxGCD(int n){ // Return max GCD return (n / 2);}// Driver code public static void main(String[] args) { int n = 4; System.out.print(maxGCD(n));} } // This code is contributed by Dewanti |
Python3
# Python3 implementation of the# above approach # Function to find the maximum GCD# among all the pairs from first n# natural numbersdef maxGCD(n): # Return max GCD return (n // 2);# Driver codeif __name__ == '__main__': n = 4; print(maxGCD(n));# This code is contributed by Amit Katiyar |
C#
// C# implementation of // the above approach using System;class GFG{ // Function to find the maximum GCD// among all the pairs from// first n natural numbersstatic int maxGCD(int n){ // Return max GCD return (n / 2);}// Driver code public static void Main(String[] args) { int n = 4; Console.Write(maxGCD(n));} } // This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript implementation of the above approach// Function to find the maximum GCD// among all the pairs from// first n natural numbersfunction maxGCD(n){ // Return max GCD return parseInt(n / 2);}// Driver Codevar n = 4;document.write( maxGCD(n));// This code is contributed by rrrtnx.</script> |
Output:
2
Time Complexity: O(1)
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!
