Encuentre el GCD mínimo de todos los pares en una array

Dada una array arr de enteros positivos, la tarea es encontrar el MCD mínimo posible para cualquier par de la array dada.
Ejemplos: 

Entrada: arr[] = {1, 2, 3, 4, 5} 
Salida: 1 
Explicación: 
GCD(1, 2) = 1.
Entrada: arr[] = {2, 4, 6, 8, 3} 
Salida: 1 

Enfoque: 
si observamos con claridad, notaremos que el MCD mínimo de dos números cualesquiera será el MCD de todos los elementos del arreglo. La razón detrás de esta observación es que el GCD mínimo para cualquier par ocurre si el elemento que minimiza el GCD de toda la array está presente en ese par.  

Ilustración: 
Consideremos una array arr[] = {2,4,6,8,3}. 
El MCD de todos los elementos del arreglo excepto 3 es 2. Al considerar 3, el mcd se minimiza a 1. El 
MCD de todos los pares posibles son: 
mcd(2,4) = 2 
mcd(2,6) = 2 
mcd(2,8) ) = 2 
mcd(2,3) = 1 
mcd(4,6) = 2 
mcd(4,8) = 4 
mcd(4,3) = 1 
mcd(6,3) = 3 
mcd(6,8) = 2 
mcd(8,3) = 1 
Por lo tanto, el mcd mínimo para cualquier par es igual a 1, que es igual al mcd del arreglo y solo aparece para los pares que contienen 3 en él. 

El siguiente código es la implementación del enfoque anterior:  

// C++ program to find the
// minimum GCD of any pair
// in the array
#include <bits/stdc++.h>
using namespace std;
 
// Function returns the
// Minimum GCD of any pair
int MinimumGCD(int arr[], int n)
{
    int g = 0;
 
    // Finding GCD of all the
    // elements in the array.
    for (int i = 0; i < n; i++) {
        g = __gcd(g, arr[i]);
    }
    return g;
}
 
// Driver code
int main()
{
    int arr[] = { 2, 4, 6, 8, 3 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    cout << MinimumGCD(arr, N) << endl;
}

// Java program to find the
// minimum GCD of any pair
// in the array
import java.util.*;
 
class GFG{
     
static int __gcd(int a, int b)
{
    if(b == 0)
        return a;
    else
        return __gcd(b, a % b);
}
 
// Function returns the
// minimum GCD of any pair
static int MinimumGCD(int arr[], int n)
{
    int g = 0;
 
    // Finding GCD of all the
    // elements in the array.
    for(int i = 0; i < n; i++)
    {
       g = __gcd(g, arr[i]);
    }
     
    return g;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { 2, 4, 6, 8, 3 };
    int N = arr.length;
 
    System.out.println(MinimumGCD(arr, N));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program to find the
# minimum GCD of any pair
# in the array
 
from math import gcd
 
# Function returns the
# Minimum GCD of any pair
def MinimumGCD(arr, n):
    g = 0
 
    # Finding GCD of all the
    # elements in the array.
    for i in range(n):
        g = gcd(g, arr[i])
    return g
 
# Driver code
if __name__ == '__main__':
     
    arr = [ 2, 4, 6, 8, 3 ]
 
    N = len(arr)
    print(MinimumGCD(arr, N))
 
# This code is contributed by Samarth

// C# program to find the
// minimum GCD of any pair
// in the array
using System;
 
class GFG{
     
static int __gcd(int a, int b)
{
    if(b == 0)
        return a;
    else
        return __gcd(b, a % b);
}
 
// Function returns the
// minimum GCD of any pair
static int MinimumGCD(int []arr, int n)
{
    int g = 0;
 
    // Finding GCD of all the
    // elements in the array.
    for(int i = 0; i < n; i++)
    {
       g = __gcd(g, arr[i]);
    }
     
    return g;
}
 
// Driver code
public static void Main(String[] args)
{
    int []arr = { 2, 4, 6, 8, 3 };
    int N = arr.Length;
 
    Console.WriteLine(MinimumGCD(arr, N));
}
}
 
// This code is contributed by sapnasingh4991

<script>
 
// JavaScript program to find the
// minimum GCD of any pair
// in the array
 
function calGCD(a, b) {
  if (!b) {
    return a;
  }
 
  return calGCD(b, a % b);
}
 
// Function returns the
// Minimum GCD of any pair
function MinimumGCD(arr, n)
{
    var g = 0;
    var i;
    // Finding GCD of all the
    // elements in the array.
    for (i = 0; i < n; i++) {
        g = calGCD(g, arr[i]);
    }
    return g;
}
 
// Driver code
    var arr = [2, 4, 6, 8, 3];
    var N = arr.length;
    document.write(MinimumGCD(arr, N));
 
</script>

1

Complejidad temporal: O(N)
Espacio auxiliar: O(1)