Find minimum GCD of all pairs in an array
Given an array arr of positive integers, the task is to find the minimum GCD possible for any pair of the given array.
Examples:
Input: arr[] = {1, 2, 3, 4, 5}
Output: 1
Explanation:
GCD(1, 2) = 1.Input: arr[] = {2, 4, 6, 8, 3}
Output: 1
Naive approach: Generate all the pairs of elements and take GCD of them, finally minimizing the output with the result.
- Initialize the result with the maximum possible gcd
- Iterate over the array
- Generate every pair
- Find the gcd of pair of elements
- Minimize the result with output.
- Return result
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; int find_min_GCD_Pair( int arr[], int N) { // Initialise the result with maximum possible gcd int result = INT_MAX; // Iterate over the array for ( int i = 0; i < N; i++) { // Generate every pair for ( int j = i + 1; j < N; j++) { // Find the gcd of pair of elements int gcd = __gcd(arr[i], arr[j]); // Minimise the result with output. result = min(result, gcd); } } // return result return result; } int main() { int arr[] = { 6, 10, 15 }; int N = 3; cout << find_min_GCD_Pair(arr, N); return 0; } |
Python3
# Python Equivalent import math def find_min_GCD_Pair(arr, N): # Initialise the result with maximum possible gcd result = float ( 'inf' ) # Iterate over the array for i in range (N): # Generate every pair for j in range (i + 1 , N): # Find the gcd of pair of elements gcd = math.gcd(arr[i], arr[j]) # Minimise the result with output. result = min (result, gcd) # return result return result if __name__ = = "__main__" : arr = [ 6 , 10 , 15 ] N = 3 print (find_min_GCD_Pair(arr, N)) |
Java
// Java program for the above approach import java.util.*; public class Main { public static int findMinGCDPair( int [] arr, int n) { // Initialize the result with maximum possible gcd int result = Integer.MAX_VALUE; // Iterate over the array for ( int i = 0 ; i < n; i++) { // Generate every pair for ( int j = i + 1 ; j < n; j++) { // Find the gcd of pair of elements int gcd = gcd(arr[i], arr[j]); // Minimise the result with output. result = Math.min(result, gcd); } } // return result return result; } public static int gcd( int a, int b) { if (b == 0 ) { return a; } return gcd(b, a % b); } public static void main(String[] args) { int [] arr = { 6 , 10 , 15 }; int n = 3 ; System.out.println(findMinGCDPair(arr, n)); } } // Contributed by adityasharmadev01 |
Javascript
// JS Equivalent const findMinGCDPair = (arr, N) => { // Initialise the result with maximum possible gcd let result = Infinity; // Iterate over the array for (let i = 0; i < N; i++) { // Generate every pair for (let j = i + 1; j < N; j++) { // Find the gcd of pair of elements let gcd = gcdFunc(arr[i], arr[j]); // Minimise the result with output. result = Math.min(result, gcd); } } // return result return result; } const gcdFunc = (a, b) => { if (b === 0) { return a; } return gcdFunc(b, a % b); }; const arr = [6, 10, 15]; const N = 3; console.log(findMinGCDPair(arr, N)); |
C#
// C# code addition using System; using System.Collections; using System.Collections.Generic; using System.Linq; class Program { public static int _gcd( int a, int b) { if (a == 0) return b; return _gcd(b % a, a); } // The function finds the minimum gcd pair public static int find_min_GCD_Pair( int [] arr, int N) { // Initialise the result with maximum possible gcd int result = int .MaxValue; // Iterate over the array for ( int i = 0; i < N; i++) { // Generate every pair for ( int j = i + 1; j < N; j++) { // Find the gcd of pair of elements int gcd = _gcd(arr[i], arr[j]); // Minimise the result with output. result = Math.Min(result, gcd); } } // return result return result; } // Driver code. static void Main() { int [] arr = { 6, 10, 15 }; int N = 3; Console.WriteLine(find_min_GCD_Pair(arr, N)); } } // The code is contributed by Arushi Goel. |
Output
2
Time Complexity: O(N2), where N is the length of the given input array.
Auxiliary Space: O(1)