Compruebe si una array se puede dividir en subarreglos con GCD superior a K

Dada una array arr[] de N enteros y un entero positivo K , la tarea es verificar si es posible dividir esta array en distintas subarreglas contiguas de modo que el máximo común divisor de todos los elementos de cada subarreglo sea mayor que K .

Nota: Cada elemento del arreglo puede ser parte de exactamente un subarreglo.

Ejemplos:

Entrada: arr[] = {3, 2, 4, 4, 8}, K = 1
Salida: Sí
Explicación:
Una división válida es [3], [2, 4], [4, 8] con GCD 3, 2 y 4 respectivamente. 
Otra división válida es [3], [2, 4], [4], [8] con GCD 3, 2, 4 y 8 respectivamente.
Por lo tanto, la array dada se puede dividir en subarreglos que tienen GCD > K.

Entrada: arr[] = {2, 4, 6, 1, 8, 16}, K = 3
Salida: No

Enfoque: Este problema se puede resolver utilizando las siguientes observaciones:

• Si se encuentra que cualquier elemento de la array es menor o igual que K , la respuesta siempre es «No». Esto se debe a que el subarreglo que contiene este número siempre tendrá GCD menor o igual a K .
• Si no se encuentra que ningún elemento de la array sea menor o igual que K , entonces siempre es posible dividir la array completa en N subarreglos, cada uno de tamaño al menos 1 cuyo GCD siempre es mayor que K .

Por lo tanto, a partir de las observaciones anteriores, la idea es atravesar la array dada y verificar si existe algún elemento en la array que sea menor o igual que K . Si se encuentra que es cierto, escriba “No” . De lo contrario, escriba «Sí» .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <iostream>
using namespace std;
 
// Function to check if it is possible
// to split an array into subarrays
// having GCD at least K
string canSplitArray(int arr[], int n,
                     int k)
{
 
    // Iterate over the array arr[]
    for (int i = 0; i < n; i++) {
 
        // If the current element
        // is less than or equal to k
        if (arr[i] <= k) {
            return "No";
        }
    }
 
    // If no array element is found
    // to be less than or equal to k
    return "Yes";
}
 
// Driver Code
int main()
{
    // Given array arr[]
    int arr[] = { 2, 4, 6, 1, 8, 16 };
 
    int N = sizeof arr / sizeof arr[0];
 
    // Given K
    int K = 3;
 
    // Function Call
    cout << canSplitArray(arr, N, K);
}

// Java program for the above approach
import java.io.*;
 
class GFG{
     
// Function to check if it is possible
// to split an array into subarrays
// having GCD at least K
static String canSplitArray(int arr[],
                            int n, int k)
{
     
    // Iterate over the array arr[]
    for(int i = 0; i < n; i++)
    {
         
        // If the current element
        // is less than or equal to k
        if (arr[i] <= k)
        {
            return "No";
        }
    }
     
    // If no array element is found
    // to be less than or equal to k
    return "Yes";
}
 
// Driver code
public static void main (String[] args)
{
     
    // Given array arr[]
    int arr[] = { 2, 4, 6, 1, 8, 16 };
     
    // Length of the array
    int N = arr.length;
     
    // Given K
    int K = 3;
     
    // Function call
    System.out.println(canSplitArray(arr, N, K));
}
}
 
// This code is contributed by jana_sayantan

# Python3 program for the above approach
 
# Function to check if it is possible
# to split an array into subarrays
# having GCD at least K
def canSplitArray(arr, n, k):
 
    # Iterate over the array arr[]
    for i in range(n):
 
        # If the current element
        # is less than or equal to k
        if (arr[i] <= k):
            return "No"
 
    # If no array element is found
    # to be less than or equal to k
    return "Yes"
 
# Driver Code
if __name__ == '__main__':
 
    # Given array arr[]
    arr = [ 2, 4, 6, 1, 8, 16 ]
 
    N = len(arr)
 
    # Given K
    K = 3
 
    # Function call
    print(canSplitArray(arr, N, K))
 
# This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
 
class GFG{
     
// Function to check if it is possible
// to split an array into subarrays
// having GCD at least K
static String canSplitArray(int []arr,
                            int n, int k)
{
     
    // Iterate over the array []arr
    for(int i = 0; i < n; i++)
    {
         
        // If the current element
        // is less than or equal to k
        if (arr[i] <= k)
        {
            return "No";
        }
    }
     
    // If no array element is found
    // to be less than or equal to k
    return "Yes";
}
 
// Driver code
public static void Main(String[] args)
{
     
    // Given array []arr
    int []arr = { 2, 4, 6, 1, 8, 16 };
     
    // Length of the array
    int N = arr.Length;
     
    // Given K
    int K = 3;
     
    // Function call
    Console.WriteLine(canSplitArray(arr, N, K));
}
}
 
// This code is contributed by Amit Katiyar

<script>
 
// JavaScript implementation of the above approach
 
// Function to check if it is possible
// to split an array into subarrays
// having GCD at least K
function canSplitArray(arr, n, k)
{
       
    // Iterate over the array arr[]
    for(let i = 0; i < n; i++)
    {
           
        // If the current element
        // is less than or equal to k
        if (arr[i] <= k)
        {
            return "No";
        }
    }
       
    // If no array element is found
    // to be less than or equal to k
    return "Yes";
}
 
// Driver code
         
    // Given array arr[]
    let arr = [ 2, 4, 6, 1, 8, 16 ];
       
    // Length of the array
    let N = arr.length;
       
    // Given K
    let K = 3;
       
    // Function call
    document.write(canSplitArray(arr, N, K));
       
    // This code is contributed by code_hunt.
</script>

No

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