Given an integer N (> 2), the task is to find the maximum GCD among all pairs possible by the integers in the range [1, N].
Example:
Input: N = 5
Output: 2
Explanation :
GCD(1, 2) : 1
GCD(1, 3) : 1
GCD(1, 4) : 1
GCD(1, 5) : 1
GCD(2, 3) : 1
GCD(2, 4) : 2
GCD(2, 5) : 1
GCD(3, 4) : 1
GCD(3, 5) : 1
GCD(4, 5) : 1Input: N = 6
Output: 3
Explanation: GCD of pair (3, 6) is the maximum.
Naive Approach:
The simplest approach to solve the problem is to generate all possible pairs from [1, N] and calculate GCD of each pair. Finally, print the maximum GCD obtained.
Time Complexity: O(N2logN)
Auxiliary Space: O(1)
Efficient Approach:
Follow the steps below to solve the problem:
- Since all the pairs are distinct, then, for any pair {a, b} with GCD g, either of a or b is greater than g.
- Considering b to be the greater number, b > 2g, since 2g is the smallest multiple of g greater than it.
- Since b cannot exceed N, and 2g <= N.
- Therefore, g = floor(n/2).
- Therefore, the maximum GCD that can be obtained is floor(n/2), when pair chosen is (floor(n/2), 2*floor(n/2)).
Illustration:
N = 6
Maximum GCD = 6/2 = 3, occurs for the pair (3, 6)
Below is the implementation of the above approach:
C++
// C++ Program to implement// the approach#include <bits/stdc++.h>using namespace std;// Function to obtain the maximum// gcd of all pairs from 1 to nvoid find(int n){ // Print the answer cout << n / 2 << endl;}// Driver codeint main(){ int n = 5; // Function call find(n); return 0;} |
Java
// Java Program to implement// the approachclass GFG{ // Function to obtain the maximum// gcd of all pairs from 1 to nstatic void find(int n){ // Print the answer System.out.println(n / 2);} // Driver codepublic static void main(String[] args){ int n = 5; // Function call find(n);}}// This code is contributed by Ritik Bansal |
Python3
# Python3 program to implement # the approach # Function to obtain the maximum # gcd of all pairs from 1 to n def find(n): # Print the answer print(n // 2)# Driver Codeif __name__ == '__main__': # Given n n = 5 # Function call find(n)# This code is contributed by Shivam Singh |
C#
// C# Program to implement// the approachusing System;class GFG{ // Function to obtain the maximum// gcd of all pairs from 1 to nstatic void find(int n){ // Print the answer Console.Write(n / 2);} // Driver codepublic static void Main(string[] args){ int n = 5; // Function call find(n);}} // This code is contributed by rock_cool |
Javascript
<script>// Javascript program to implement// the approach// Function to obtain the maximum// gcd of all pairs from 1 to nfunction find(n){ // Print the answer document.write(parseInt(n / 2, 10) + "</br>");}// Driver codelet n = 5;// Function callfind(n);// This code is contributed by divyeshrabadiya07</script> |
2
Time Complexity: O(1)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
