Eliminaciones mínimas requeridas para hacer que el GCD de la array sea igual a 1

Dada una array arr[] de N enteros, la tarea es encontrar las eliminaciones mínimas requeridas para hacer que el GCD de los elementos resultantes de la array sea igual a 1 . Si es imposible, imprima -1 .
Ejemplos: 
 

Entrada: arr[] = {2, 4, 6, 3} 
Salida: 0 
Está claro que GCD(2, 4, 6, 3) = 1 
Por lo tanto, no necesitamos eliminar ningún elemento.
Entrada: arr[] = {8, 14, 16, 26} 
Salida: -1 
No importa cuántos elementos se eliminen, el gcd nunca será 1. 
 

Enfoque: si el GCD de la array inicial es 1, entonces no necesitamos eliminar ninguno de los elementos y el resultado será 0. Si GCD no es 1, entonces el GCD nunca puede ser 1 sin importar qué elementos eliminemos. Digamos que mcd es el mcd de los elementos del arreglo y eliminamos k elementos. Ahora, quedan N – k elementos y todavía tienen gcd como su factor. Por lo tanto, es imposible obtener GCD de los elementos de la array igual a 1 .
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the minimum
// deletions required
int MinDeletion(int a[], int n)
{
 
    // To store the GCD of the array
    int gcd = 0;
    for (int i = 0; i < n; i++)
        gcd = __gcd(gcd, a[i]);
 
    // GCD cannot be 1
    if (gcd > 1)
        return -1;
 
    // GCD of the elements is already 1
    else
        return 0;
}
 
// Driver code
int main()
{
    int a[] = { 3, 6, 12, 81, 9 };
    int n = sizeof(a) / sizeof(a[0]);
 
    cout << MinDeletion(a, n);
 
    return 0;
}

// Java implementation of the approach
import java.io.*;
 
class GFG
{
 
    // Recursive function to return gcd of a and b
    static int __gcd(int a, int b)
    {
        // Everything divides 0
        if (a == 0)
        return b;
        if (b == 0)
        return a;
         
        // base case
        if (a == b)
            return a;
         
        // a is greater
        if (a > b)
            return __gcd(a-b, b);
        return __gcd(a, b-a);
    }
 
    // Function to return the minimum
    // deletions required
    static int MinDeletion(int a[], int n)
    {
     
        // To store the GCD of the array
        int gcd = 0;
        for (int i = 0; i < n; i++)
            gcd = __gcd(gcd, a[i]);
     
        // GCD cannot be 1
        if (gcd > 1)
            return -1;
     
        // GCD of the elements is already 1
        else
            return 0;
    }
 
 
    // Driver code
    public static void main (String[] args)
    {
        int a[] = { 3, 6, 12, 81, 9 };
        int n = a.length;
 
        System.out.print(MinDeletion(a, n));
    }
}
 
// This code is contributed by anuj_67..

# Python3 implementation of the approach
from math import gcd
 
# Function to return the minimum
# deletions required
def MinDeletion(a, n) :
 
    # To store the GCD of the array
    __gcd = 0;
    for i in range(n) :
        __gcd = gcd(__gcd, a[i]);
 
    # GCD cannot be 1
    if (__gcd > 1) :
        return -1;
 
    # GCD of the elements is already 1
    else :
        return 0;
 
# Driver code
if __name__ == "__main__" :
 
    a = [ 3, 6, 12, 81, 9 ];
    n = len(a)
 
    print(MinDeletion(a, n));
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
 
class GFG
{
 
    // Recursive function to return gcd of a and b
    static int __gcd(int a, int b)
    {
        // Everything divides 0
        if (a == 0)
            return b;
        if (b == 0)
            return a;
         
        // base case
        if (a == b)
            return a;
         
        // a is greater
        if (a > b)
            return __gcd(a-b, b);
        return __gcd(a, b-a);
    }
 
    // Function to return the minimum
    // deletions required
    static int MinDeletion(int []a, int n)
    {
     
        // To store the GCD of the array
        int gcd = 0;
        for (int i = 0; i < n; i++)
            gcd = __gcd(gcd, a[i]);
     
        // GCD cannot be 1
        if (gcd > 1)
            return -1;
     
        // GCD of the elements is already 1
        else
            return 0;
    }
 
 
    // Driver code
    public static void Main ()
    {
        int []a = { 3, 6, 12, 81, 9 };
        int n = a.Length;
 
        Console.WriteLine(MinDeletion(a, n));
    }
}
 
// This code is contributed by anuj_67..

<script>
// javascript implementation of the approach
 
    // Recursive function to return gcd of a and b
    function __gcd(a , b) {
        // Everything divides 0
        if (a == 0)
            return b;
        if (b == 0)
            return a;
 
        // base case
        if (a == b)
            return a;
 
        // a is greater
        if (a > b)
            return __gcd(a - b, b);
        return __gcd(a, b - a);
    }
 
    // Function to return the minimum
    // deletions required
    function MinDeletion(a , n) {
 
        // To store the GCD of the array
        var gcd = 0;
        for (i = 0; i < n; i++)
            gcd = __gcd(gcd, a[i]);
 
        // GCD cannot be 1
        if (gcd > 1)
            return -1;
 
        // GCD of the elements is already 1
        else
            return 0;
    }
 
    // Driver code
     
        var a = [ 3, 6, 12, 81, 9 ];
        var n = a.length;
 
        document.write(MinDeletion(a, n));
 
// This code is contributed by aashish1995
</script>

-1

Complejidad de tiempo: O(N)

Espacio Auxiliar: O(1)