Dada una array arr[] que consta de N enteros, la tarea es reemplazar un número mínimo de pares de elementos adyacentes por su suma para hacer que todos los elementos de la array sean iguales . Imprima el número mínimo de tales operaciones requeridas.
Ejemplos:
Entrada: arr[] = {1, 2, 3}
Salida: 1
Explicación: Reemplace arr[0] y arr[1] por su suma. Por lo tanto, la array se modifica a {3, 3}.
Después de completar las operaciones anteriores, todos los elementos de la array se vuelven iguales.
Por lo tanto, el número de operaciones requeridas es 1.Entrada: arr[] = {4, 4, 4}
Salida: 0
Enfoque: El problema dado se puede resolver utilizando la técnica Prefix Sum Array . Siga los pasos a continuación para resolver el problema dado:
- Inicialice una variable, digamos count , para almacenar el recuento máximo de subarreglos que se pueden obtener para cualquier valor de suma dado.
- Inicialice una array auxiliar prefijo[] , de tamaño N , y almacene la suma del prefijo de la array dada arr[] en ella.
- Atraviese el prefijo[] de la array y para cada elemento prefijo[i] , realice los siguientes pasos:
- Compruebe si la array dada arr[] se puede dividir en subarreglos con el prefijo suma[i] o no. Si se encuentra que es true , almacene el recuento de dichos subarreglos en una variable, digamos ans .
- Actualice el valor de count como el máximo de count y ans .
- Después de completar los pasos anteriores, imprima el valor de (N – conteo) como el número mínimo de operaciones requeridas.
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 to count the minimum number
// of pairs of adjacent elements required
// to be replaced by their sum to make all
// array elements equal
int minSteps(vector<int> a, int n)
{
// Stores the prefix sum of the array
vector<int> prefix_sum(n);
prefix_sum[0] = a[0];
// Calculate the prefix sum array
for (int i = 1; i < n; i++)
prefix_sum[i] += prefix_sum[i - 1] + a[i];
// Stores the maximum number of subarrays
// into which the array can be split
int mx = -1;
// Iterate over all possible sums
for (int subgroupsum :prefix_sum)
{
int sum = 0;
int i = 0;
int grp_count = 0;
// Traverse the array
while (i < n)
{
sum += a[i];
// If the sum is equal to
// the current prefix sum
if (sum == subgroupsum)
{
// Increment count
// of groups by 1
grp_count += 1;
sum = 0;
}
// Otherwise discard
// this subgroup sum
else if(sum > subgroupsum)
{
grp_count = -1;
break;
}
i += 1;
}
// Update the maximum
// this of subarrays
if (grp_count > mx)
mx = grp_count;
}
// Return the minimum
// number of operations
return n - mx;
}
// Driver Code
int main()
{
vector<int> A = {1, 2, 3, 2, 1, 3};
int N = A.size();
// Function Call
cout << minSteps(A, N);
return 0;
}
// This code is contributed by mohit kumar 29.
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to count the minimum number
// of pairs of adjacent elements required
// to be replaced by their sum to make all
// array elements equal
static int minSteps(ArrayList<Integer> a, int n)
{
// Stores the prefix sum of the array
int []prefix_sum = new int[n];
prefix_sum[0] = a.get(0);
// Calculate the prefix sum array
for(int i = 1; i < n; i++)
prefix_sum[i] += prefix_sum[i - 1] + a.get(i);
// Stores the maximum number of subarrays
// into which the array can be split
int mx = -1;
// Iterate over all possible sums
for(int subgroupsum : prefix_sum)
{
int sum = 0;
int i = 0;
int grp_count = 0;
// Traverse the array
while (i < n)
{
sum += a.get(i);
// If the sum is equal to
// the current prefix sum
if (sum == subgroupsum)
{
// Increment count
// of groups by 1
grp_count += 1;
sum = 0;
}
// Otherwise discard
// this subgroup sum
else if(sum > subgroupsum)
{
grp_count = -1;
break;
}
i += 1;
}
// Update the maximum
// this of subarrays
if (grp_count > mx)
mx = grp_count;
}
// Return the minimum
// number of operations
return n - mx;
}
// Driver Code
public static void main(String[] args)
{
ArrayList<Integer>A = new ArrayList<Integer>();
A.add(1);
A.add(2);
A.add(3);
A.add(2);
A.add(1);
A.add(3);
int N = A.size();
// Function Call
System.out.print(minSteps(A, N));
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program for the above approach # Function to count the minimum number # of pairs of adjacent elements required # to be replaced by their sum to make all # array elements equal def minSteps(a, n): # Stores the prefix sum of the array prefix_sum = a[:] # Calculate the prefix sum array for i in range(1, n): prefix_sum[i] += prefix_sum[i-1] # Stores the maximum number of subarrays # into which the array can be split mx = -1 # Iterate over all possible sums for subgroupsum in prefix_sum: sum = 0 i = 0 grp_count = 0 # Traverse the array while i < n: sum += a[i] # If the sum is equal to # the current prefix sum if sum == subgroupsum: # Increment count # of groups by 1 grp_count += 1 sum = 0 # Otherwise discard # this subgroup sum elif sum > subgroupsum: grp_count = -1 break i += 1 # Update the maximum # this of subarrays if grp_count > mx: mx = grp_count # Return the minimum # number of operations return n - mx # Driver Code if __name__ == '__main__': A = [1, 2, 3, 2, 1, 3] N = len(A) # Function Call print(minSteps(A, N))
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to count the minimum number
// of pairs of adjacent elements required
// to be replaced by their sum to make all
// array elements equal
static int minSteps(List<int> a, int n)
{
// Stores the prefix sum of the array
int []prefix_sum = new int[n];
prefix_sum[0] = a[0];
// Calculate the prefix sum array
for (int i = 1; i < n; i++)
prefix_sum[i] += prefix_sum[i - 1] + a[i];
// Stores the maximum number of subarrays
// into which the array can be split
int mx = -1;
// Iterate over all possible sums
foreach (int subgroupsum in prefix_sum)
{
int sum = 0;
int i = 0;
int grp_count = 0;
// Traverse the array
while (i < n)
{
sum += a[i];
// If the sum is equal to
// the current prefix sum
if (sum == subgroupsum)
{
// Increment count
// of groups by 1
grp_count += 1;
sum = 0;
}
// Otherwise discard
// this subgroup sum
else if(sum > subgroupsum)
{
grp_count = -1;
break;
}
i += 1;
}
// Update the maximum
// this of subarrays
if (grp_count > mx)
mx = grp_count;
}
// Return the minimum
// number of operations
return n - mx;
}
// Driver Code
public static void Main()
{
List<int> A = new List<int>(){1, 2, 3, 2, 1, 3};
int N = A.Count;
// Function Call
Console.Write(minSteps(A, N));
}
}
// This code is contributed by SURENDRA_GANGWAR.
Javascript
<script>
// Javascript program for the above approach
// Function to count the minimum number
// of pairs of adjacent elements required
// to be replaced by their sum to make all
// array elements equal
function minSteps(a, n)
{
// Stores the prefix sum of the array
var prefix_sum = Array(n).fill(0);
prefix_sum[0] = a[0];
// Calculate the prefix sum array
for (var i = 1; i < n; i++)
prefix_sum[i] += prefix_sum[i - 1] + a[i];
// Stores the maximum number of subarrays
// into which the array can be split
var mx = -1;
// Iterate over all possible sums
for (var subgroupsum =0;
subgroupsum<prefix_sum.length; subgroupsum++)
{
var sum = 0;
var i = 0;
var grp_count = 0;
// Traverse the array
while (i < n)
{
sum += a[i];
// If the sum is equal to
// the current prefix sum
if (sum == prefix_sum[subgroupsum])
{
// Increment count
// of groups by 1
grp_count += 1;
sum = 0;
}
// Otherwise discard
// this subgroup sum
else if(sum > prefix_sum[subgroupsum])
{
grp_count = -1;
break;
}
i += 1;
}
// Update the maximum
// this of subarrays
if (grp_count > mx)
mx = grp_count;
}
// Return the minimum
// number of operations
return n - mx;
}
// Driver Code
var A = [1, 2, 3, 2, 1, 3];
var N = A.length;
// Function Call
document.write( minSteps(A, N));
</script>
Producción:
2
Complejidad de tiempo : O(N 2 ), ya que estamos usando bucles anidados para atravesar N 2 veces.
Espacio auxiliar : O(N), ya que estamos usando espacio adicional para prefix_sum.
Publicación traducida automáticamente
Artículo escrito por mukulbindal170299 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA