Dada una array de enteros arr[], la tarea es minimizar la longitud de la array dada reemplazando repetidamente dos elementos de array adyacentes desiguales por su suma. Una vez que la array se reduce a su longitud mínima posible, es decir, no quedan pares desiguales adyacentes en la array, imprima la cuenta de operaciones requeridas.
Ejemplos:
Entrada: arr[] = {2, 1, 3, 1}
Salida: 1
Explicación:
Operación 1: { 2, 1, 3, 1} -> { 3 , 3, 1}
Operación 2: {3, 3, 1 } -> {3, 4}
Operación 3: {3, 4} -> {7}
Por lo tanto, la longitud mínima a la que se puede reducir la array es 1.Entrada: arr[] = {1, 1, 1, 1}
Salida: 4
Explicación:
No es posible la operación de fusión ya que no se pueden obtener pares adyacentes desiguales.
Por lo tanto, la longitud mínima de la array es 4.
Enfoque ingenuo: el enfoque más simple para resolver el problema es atravesar la array dada y, para cada par desigual adyacente, reemplazar el par por su suma. Finalmente, si no existe un par desigual en la array, imprima la longitud de la array.
Complejidad de tiempo: O(N 2 ), ya que tenemos que usar bucles anidados para atravesar N*N veces.
Espacio Auxiliar : O(N), ya que tenemos que usar espacio extra.
Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones:
- Si todos los elementos de la array son iguales, no se puede realizar ninguna operación. Por lo tanto, imprima N , es decir, la longitud inicial de la array, como la longitud mínima reducible de la array
- De lo contrario, la longitud mínima de la array siempre será 1 .
Por lo tanto, para resolver el problema, simplemente recorra la array y verifique si todos los elementos de la array son iguales o no. Si se encuentra que es cierto, escriba N como la respuesta requerida. De lo contrario, imprima 1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function that returns the minimum
// length of the array after merging
// unequal adjacent elements
int minLength(int A[], int N)
{
// Stores the first element
// and its frequency
int elem = A[0], count = 1;
// Traverse the array
for (int i = 1; i < N; i++) {
if (A[i] == elem) {
count++;
}
else {
break;
}
}
// If all elements are equal
if (count == N)
// No merge-pair operations
// can be performed
return N;
// Otherwise
else
return 1;
}
// Driver Code
int main()
{
// Given array
int arr[] = { 2, 1, 3, 1 };
// Length of the array
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << minLength(arr, N) << endl;
return 0;
}
Java
// Java program for
// the above approach
class GFG{
// Function that returns the minimum
// length of the array
// after merging unequal
// adjacent elements
static int minLength(int A[],
int N)
{
// Stores the first element
// and its frequency
int elem = A[0], count = 1;
// Traverse the array
for (int i = 1; i < N; i++)
{
if (A[i] == elem)
{
count++;
}
else
{
break;
}
}
// If all elements are equal
if (count == N)
// No merge-pair operations
// can be performed
return N;
// Otherwise
else
return 1;
}
// Driver Code
public static void main(String[] args)
{
// Given array
int arr[] = {2, 1, 3, 1};
// Length of the array
int N = arr.length;
// Function Call
System.out.print(minLength(arr, N) + "\n");
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program for the above approach # Function that returns the minimum # length of the array after merging # unequal adjacent elements def minLength(A, N): # Stores the first element # and its frequency elem = A[0] count = 1 # Traverse the array for i in range(1, N): if (A[i] == elem): count += 1 else: break # If all elements are equal if (count == N): # No merge-pair operations # can be performed return N # Otherwise else: return 1 # Driver Code # Given array arr = [ 2, 1, 3, 1 ] # Length of the array N = len(arr) # Function call print(minLength(arr, N)) # This code is contributed by code_hunt
C#
// C# program for
// the above approach
using System;
class GFG{
// Function that returns the minimum
// length of the array
// after merging unequal
// adjacent elements
static int minLength(int []A,
int N)
{
// Stores the first element
// and its frequency
int elem = A[0], count = 1;
// Traverse the array
for (int i = 1; i < N; i++)
{
if (A[i] == elem)
{
count++;
}
else
{
break;
}
}
// If all elements are equal
if (count == N)
// No merge-pair operations
// can be performed
return N;
// Otherwise
else
return 1;
}
// Driver Code
public static void Main(String[] args)
{
// Given array
int []arr = {2, 1, 3, 1};
// Length of the array
int N = arr.Length;
// Function Call
Console.Write(minLength(arr, N) + "\n");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program for
// the above approach
// Function that returns the minimum
// length of the array
// after merging unequal
// adjacent elements
function minLength(A , N)
{
// Stores the first element
// and its frequency
var elem = A[0], count = 1;
// Traverse the array
for (var i = 1; i < N; i++) {
if (A[i] == elem) {
count++;
} else {
break;
}
}
// If all elements are equal
if (count == N)
// No merge-pair operations
// can be performed
return N;
// Otherwise
else
return 1;
}
// Driver Code
// Given array
var arr = [ 2, 1, 3, 1 ];
// Length of the array
var N = arr.length;
// Function Call
document.write(minLength(arr, N) + "\n");
// This code contributed by aashish1995
</script>
1
Complejidad de tiempo : O (N), ya que estamos usando un bucle para atravesar N veces.
Espacio auxiliar : O(1), ya que no estamos utilizando ningún espacio adicional.