Conjunto más pequeño que se puede obtener reemplazando pares adyacentes con sus productos

Dada una array arr[] de tamaño N, la tarea es imprimir el tamaño mínimo posible al que se puede reducir la array dada realizando las siguientes operaciones: 

• Elimine dos elementos adyacentes, digamos arr[i] y arr[i+1] e inserte un solo elemento arr[i] * arr[i+1] en esa posición en la array.
• Si todos los elementos de la array se vuelven iguales, imprima el tamaño de la array .

Ejemplos: 

Entrada: arr[] = {1, 7, 7, 1, 7, 1} 
Salida: 1 
Explicación: 
Elija arr[0] y arr[1] y reemplácelos con arr[0]*arr[1], arr[] = {7, 7, 1, 7, 1} 
Elija arr[0] y arr[1] y reemplácelos con arr[0]*arr[1], arr[] = {49, 1, 7, 1} 
Elija arr [0] y arr[1] y reemplazar con arr[0]*arr[1], arr[] = {49, 7, 1} 
Seleccione arr[0] y arr[1] y reemplace con arr[0]* arr[1], arr[] = {343, 1} 
Elija arr[0] y arr[1] y reemplácelos con arr[0]*arr[1], arr[] = {343} 

Entrada: arr[] = {2, 2, 2, 2} 
Salida: 4 

Enfoque: el enfoque se basa en la idea de que si todos los elementos de la array son iguales, las operaciones dadas no se pueden realizar en la array dada. De lo contrario, en todos los casos, el tamaño de la array se puede reducir a 1. A continuación se muestran los pasos:

1. Iterar sobre la array dada arr[] .
2. Si todos los elementos de la array son iguales , imprima N como la respuesta requerida.
3. De lo contrario, elija siempre elementos adyacentes que den el máximo producto para reducir el tamaño de arr[] a 1. Por lo tanto, el tamaño mínimo posible será 1 .

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

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to minimize the size of
// array by performing given operations
int minLength(int arr[], int N)
{
 
    for (int i = 1; i < N; i++) {
 
        // If all array elements
        // are not same
        if (arr[0] != arr[i]) {
            return 1;
        }
    }
 
    // If all array elements
    // are same
    return N;
}
 
// Driver Code
int main()
{
    int arr[] = { 2, 1, 3, 1 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    cout << minLength(arr, N);
 
    return 0;
}

// Java implementation of the above approach
import java.io.*;
 
class GFG{
     
// Function to minimize the size of
// array by performing given operations
static int minLength(int arr[], int N)
{
    for(int i = 1; i < N; i++)
    {
         
        // If all array elements
        // are not same
        if (arr[0] != arr[i])
        {
            return 1;
        }
    }
     
    // If all array elements
    // are same
    return N;
}
 
// Driver Code
public static void main(String[] args)
{
    int[] arr = { 2, 1, 3, 1 };
    int N = arr.length;
 
    // Function call
    System.out.print(minLength(arr, N));
}
}
 
// This code is contributed by akhilsaini

# Python3 implementation of the above approach
 
# Function to minimize the size of
# array by performing given operations
def minLength(arr, N):
     
    for i in range(1, N):
         
        # If all array elements
        # are not same
        if (arr[0] != arr[i]):
            return 1
             
    # If all array elements
    # are same
    return N
 
# Driver Code
if __name__ == "__main__":
     
    arr = [ 2, 1, 3, 1 ]
    N = len(arr)
     
    # Function call
    print(minLength(arr, N))
 
# This code is contributed by akhilsaini

// C# implementation of the above approach
using System;
 
class GFG{
     
// Function to minimize the size of
// array by performing given operations
static int minLength(int[] arr, int N)
{
    for(int i = 1; i < N; i++)
    {
         
        // If all array elements
        // are not same
        if (arr[0] != arr[i])
        {
            return 1;
        }
    }
 
    // If all array elements
    // are same
    return N;
}
 
// Driver Code
public static void Main()
{
    int[] arr = { 2, 1, 3, 1 };
    int N = arr.Length;
 
    // Function call
    Console.Write(minLength(arr, N));
}
}
 
// This code is contributed by akhilsaini

<script>
 
// Javascript program to implement
// the above approach
  
// Function to minimize the size of
// array by performing given operations
function minLength(arr, N)
{
    for(let i = 1; i < N; i++)
    {
         
        // If all array elements
        // are not same
        if (arr[0] != arr[i])
        {
            return 1;
        }
    }
     
    // If all array elements
    // are same
    return N;
}
 
// Driver Code
 
    let arr = [ 2, 1, 3, 1 ];
    let N = arr.length;
 
    // Function call
    document.write(minLength(arr, N));
 
</script>

1

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