Divida la array en un número mínimo de subarreglos que tengan un GCD de su primer y último elemento superior a 1

Dada una array arr[] de tamaño N , la tarea es dividir toda la array en un número mínimo de subarreglos de modo que para cada subarreglo , el GCD del primer y último elemento del subarreglo sea mayor que 1.

Ejemplos:

Entrada: arr[] = {2, 3, 4, 4, 4, 3} 
Salida: 2 
Explicación: 
Divide la array dada en [2, 3, 4, 4, 4] y [3]. 
El primer subarreglo tiene mcd(2, 4) = 2 que es mayor que 1 y 
el segundo subarreglo tiene mcd(3, 3) = 3 que también es mayor que 1.

Entrada: arr[] = {1, 2, 3} 
Salida: 0 
Explicación: 
No es posible dividir la array dada en subarreglos en los que el GCD del primer y último elemento del subarreglo es mayor que 1.

Enfoque ingenuo: el enfoque más simple para resolver el problema es realizar todas las divisiones posibles en la array dada y, para cada división, verificar si todas las subarreglas tienen GCD de su primer y último elemento mayor que 1 o no. Para todos los subarreglos para los que se encuentra que es cierto, almacene el recuento de subarreglos. Finalmente, imprima el conteo mínimo obtenido entre esas divisiones.
Complejidad temporal: O(2 ^N ) 
Espacio auxiliar: O(1) 

Enfoque eficiente: el enfoque se basa en la idea de que siempre se usarán el primer y el último elemento de la array original. El primer elemento se usará en la primera división del subarreglo, el último elemento se usará en la última división del subarreglo. Para minimizar el recuento de subarreglos válidos, siga los pasos a continuación:

1. Fije un puntero derecho al último elemento de la array original arr[] y busque el elemento más a la izquierda en la array original de modo que GCD(left, right) > 1 . Si no se encuentra tal elemento, no hay una respuesta válida.
2. Si se encuentra tal elemento, eso significa que hemos encontrado un subarreglo válido. Luego cambie el puntero derecho a (izquierda – 1) y comience nuevamente a buscar un subarreglo válido.
3. Repita el paso anterior hasta que la derecha sea mayor que 0 y siga aumentando el recuento de subarreglos encontrados hasta ahora.
4. Imprima el valor de conteo después de todos los pasos anteriores.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the
// minimum number of subarrays
int minSubarrays(int arr[], int n)
{
    // Right pointer
    int right = n - 1;
 
    // Left pointer
    int left = 0;
 
    // Count of subarrays
    int subarrays = 0;
 
    while (right >= 0) {
 
        for (left = 0; left <= right;
             left += 1) {
 
            // Find GCD(left, right)
            if (__gcd(arr[left],
                      arr[right])
                > 1) {
 
                // Found a valid large
                // subarray between
                // arr[left, right]
                subarrays += 1;
                right = left - 1;
                break;
            }
 
            // Searched the arr[0..right]
            // and found no subarray
            // having size >1 and having
            // gcd(left, right) > 1
            if (left == right
                && __gcd(arr[left],
                         arr[right])
                       == 1) {
                return 0;
            }
        }
    }
    return subarrays;
}
 
// Driver Code
int main()
{
    int N = 6;
    int arr[] = { 2, 3, 4, 4, 4, 3 };
 
    // Function call
    cout << minSubarrays(arr, N);
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG{
 
// Function to find the
// minimum number of subarrays
static int minSubarrays(int arr[], int n)
{
    // Right pointer
    int right = n - 1;
 
    // Left pointer
    int left = 0;
 
    // Count of subarrays
    int subarrays = 0;
 
    while (right >= 0)
    {
        for (left = 0; left <= right; left += 1)
        {
            // Find GCD(left, right)
            if (__gcd(arr[left],
                      arr[right]) > 1)
            {
                // Found a valid large
                // subarray between
                // arr[left, right]
                subarrays += 1;
                right = left - 1;
                break;
            }
 
            // Searched the arr[0..right]
            // and found no subarray
            // having size >1 and having
            // gcd(left, right) > 1
            if (left == right &&
                __gcd(arr[left],
                arr[right]) == 1)
            {
                return 0;
            }
        }
    }
    return subarrays;
}
static int __gcd(int a, int b) 
{ 
    return b == 0 ? a : __gcd(b, a % b);    
}
// Driver Code
public static void main(String[] args)
{
    int N = 6;
    int arr[] = {2, 3, 4, 4, 4, 3};
 
    // Function call
    System.out.print(minSubarrays(arr, N));
}
}
 
// This code is contributed by Rajput-Ji

# Python3 program for the above approach
from math import gcd
 
# Function to find the
# minimum number of subarrays
def minSubarrays(arr, n):
     
    # Right pointer
    right = n - 1
 
    # Left pointer
    left = 0
 
    # Count of subarrays
    subarrays = 0
 
    while (right >= 0):
        for left in range(right + 1):
 
            # Find GCD(left, right)
            if (gcd(arr[left], arr[right]) > 1):
 
                # Found a valid large
                # subarray between
                # arr[left, right]
                subarrays += 1
                right = left - 1
                break
 
            # Searched the arr[0..right]
            # and found no subarray
            # having size >1 and having
            # gcd(left, right) > 1
            if (left == right and
                __gcd(arr[left],
                      arr[right]) == 1):
                return 0
 
    return subarrays
 
# Driver Code
if __name__ == '__main__':
     
    N = 6
    arr = [ 2, 3, 4, 4, 4, 3 ]
 
    # Function call
    print(minSubarrays(arr, N))
     
# This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
class GFG{
 
// Function to find the
// minimum number of subarrays
static int minSubarrays(int[] arr, int n)
{
    // Right pointer
    int right = n - 1;
 
    // Left pointer
    int left = 0;
 
    // Count of subarrays
    int subarrays = 0;
 
    while (right >= 0)
    {
        for (left = 0; left <= right; left += 1)
        {
            // Find GCD(left, right)
            if (__gcd(arr[left],
                      arr[right]) > 1)
            {
                // Found a valid large
                // subarray between
                // arr[left, right]
                subarrays += 1;
                right = left - 1;
                break;
            }
 
            // Searched the arr[0..right]
            // and found no subarray
            // having size >1 and having
            // gcd(left, right) > 1
            if (left == right &&
                __gcd(arr[left],
                      arr[right]) == 1)
            {
                return 0;
            }
        }
    }
    return subarrays;
}
   
static int __gcd(int a, int b) 
{ 
    return b == 0 ? a : __gcd(b, a % b);    
}
   
// Driver Code
public static void Main()
{
    int N = 6;
    int[] arr = {2, 3, 4, 4, 4, 3};
 
    // Function call
    Console.Write(minSubarrays(arr, N));
}
}
 
// This code is contributed by Chitranayal

<script>
// javascript program for the above approach
 
    // Function to find the
    // minimum number of subarrays
    function minSubarrays(arr , n) {
        // Right pointer
        var right = n - 1;
 
        // Left pointer
        var left = 0;
 
        // Count of subarrays
        var subarrays = 0;
 
        while (right >= 0) {
            for (left = 0; left <= right; left += 1) {
                // Find GCD(left, right)
                if (__gcd(arr[left], arr[right]) > 1) {
                    // Found a valid large
                    // subarray between
                    // arr[left, right]
                    subarrays += 1;
                    right = left - 1;
                    break;
                }
 
                // Searched the arr[0..right]
                // and found no subarray
                // having size >1 and having
                // gcd(left, right) > 1
                if (left == right && __gcd(arr[left], arr[right]) == 1) {
                    return 0;
                }
            }
        }
        return subarrays;
    }
 
    function __gcd(a , b) {
        return b == 0 ? a : __gcd(b, a % b);
    }
 
    // Driver Code
     
        var N = 6;
        var arr = [ 2, 3, 4, 4, 4, 3 ];
 
        // Function call
        document.write(minSubarrays(arr, N));
 
// This code contributed by umadevi9616
</script>

2

Complejidad de Tiempo: O( ) 
Espacio Auxiliar: O(1)