Dada una array de enteros arr de tamaño N[] , la tarea es encontrar el subarreglo de equilibrio más largo, es decir, un subarreglo tal que la suma del prefijo de la array restante sea la misma que la suma del sufijo.
Ejemplos:
Entrada: N = 3, arr[] = {10, 20, 10}
Salida: 1
Explicación: El subarreglo más largo es {20}. El prefijo restante es {10} y el sufijo es {10}.
Por lo tanto, solo un elemento en el subarreglo.Entrada: N = 6, arr[] = {2, 1, 4, 2, 4, 1}
Salida: 0
Explicación: El subarreglo más largo es de tamaño 0.
El prefijo es {2, 1, 4} y el sufijo es { 2, 4, 1} y ambos tienen algún 7.Entrada: N = 5, arr[] = {1, 2, 4, 8, 16}
Salida: -1
Enfoque: Este problema se puede resolver con la técnica de dos punteros basada en la siguiente idea:
Atraviesa desde ambos extremos. Si la suma del prefijo es menor, incremente el puntero frontal; de lo contrario, haga lo contrario. De esta forma obtendremos el mínimo número de elementos en prefijo y sufijo. Entonces, el subarreglo tendrá la longitud máxima porque el arreglo restante tiene elementos mínimos.
Siga los pasos mencionados a continuación para implementar la idea:
- Sea i el puntero izquierdo inicialmente en 0 y j el puntero derecho inicialmente en N-1 .
- Primero, comprobaremos si la suma de todos los elementos es 0 o no. Si es 0, todo el arreglo será el subarreglo.
- Inicialice dos variables prefixSum = 0 y suffixSum = 0 .
- Traverse array desde hasta i no igual a j .
- Si prefixSum <= suffixSum , agregue arr[i] en prefixSum . E incrementa i en uno.
- De lo contrario, compruebe que si prefixSum > suffixSum , agregue add arr[i] en suffixSum . Y decrementa j en uno.
- Ahora verifique que si prefixSum es igual a suffixSum , devuelva la diferencia entre i y j .
- De lo contrario, devuelve -1.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
// C++ function to find out if prefixSum
// can be equal to the suffixSum
int isEqual(int n, int arr[])
{
// Base Case
if (n == 1) {
return -1;
}
// Checking if the sum of all elements
// is 0 or not. As the whole array can
// also be a subarray.
int sum=0;
for(int i=0;i<n;i++)
{
sum+=arr[i];
}
if(sum==0)
return n;
int prefixSum = 0, suffixSum = 0;
int i = 0, j = n - 1;
// We are assuming that the ans is No
int ans = -1;
// Iterate till there is one element in the
// array
while (i <= j) {
// If prefix sum is less or equal then
// add it in the prefix sum and
// increment i
if (prefixSum <= suffixSum) {
prefixSum += arr[i];
i++;
}
// If suffix sum is less than add it in
// the suffix sum and decrement j
else if (prefixSum > suffixSum) {
suffixSum += arr[j];
j--;
}
// Check if both are equal or not? if they
// are then make ans = "YES" and break
if (prefixSum == suffixSum) {
return j - i + 1;
}
}
if (prefixSum == suffixSum)
return 0;
// return ans;
return -1;
}
// Driver function
int main()
{
int N = 3;
int arr[] = { 10, 20, 10 };
// Function call
cout << isEqual(N, arr) << "\n";
return 0;
}
// This code is contributed by Pushpesh Raj.
Java
// Java implementation for the above approach
import java.util.*;
public class GFG {
// C# function to find out if prefixSum
// can be equal to the suffixSum
static int isEqual(int n, int[] arr)
{
// Base Case
if (n == 1) {
return -1;
}
// Checking if the sum of all elements
// is 0 or not. As the whole array can
// also be a subarray.
int sum=0;
for(int i=0;i<n;i++)
{
sum+=arr[i];
}
if(sum==0)
return n;
int prefixSum = 0, suffixSum = 0;
int i = 0, j = n - 1;
// We are assuming that the ans is No
int ans = -1;
// Iterate till there is one element in the
// array
while (i <= j) {
// If prefix sum is less or equal then
// add it in the prefix sum and
// increment i
if (prefixSum <= suffixSum) {
prefixSum += arr[i];
i++;
}
// If suffix sum is less than add it in
// the suffix sum and decrement j
else if (prefixSum > suffixSum) {
suffixSum += arr[j];
j--;
}
// Check if both are equal or not? if they
// are then make ans = "YES" and break
if (prefixSum == suffixSum) {
return j - i + 1;
}
}
if (prefixSum == suffixSum)
return 0;
// return ans;
return -1;
}
// Driver function
public static void main(String args[])
{
int N = 3;
int[] arr = { 10, 20, 10 };
// Function call
System.out.println(isEqual(N, arr));
}
}
Python3
# Python program for the above approach def isEqual(n, arr): # Base Case if (n == 1): return -1 # checking if the sum of all the elements # is 0 or not. As whole array can also # be the subarray Sum=0 for i in range(n): Sum=Sum+arr[i] if(Sum==0): return n prefixSum,suffixSum = 0,0 i,j = 0,n - 1 # We are assuming that the ans is No ans = -1 # Iterate till there is one element in the # array while (i <= j): # If prefix sum is less or equal then # add it in the prefix sum and # increment i if (prefixSum <= suffixSum): prefixSum += arr[i] i += 1 # If suffix sum is less than add it in # the suffix sum and decrement j elif (prefixSum > suffixSum): suffixSum += arr[j] j -= 1 # Check if both are equal or not? if they # are then make ans = "YES" and break if (prefixSum == suffixSum): return j - i + 1 if (prefixSum == suffixSum): return 0 # return ans; return -1 # Driver function N = 3 arr = [10, 20, 10] # Function call print(isEqual(N, arr))
C#
// C# implementation for the above approach
using System;
class GFG {
// C# function to find out if prefixSum
// can be equal to the suffixSum
static int isEqual(int n, int[] arr)
{
// Base Case
if (n == 1) {
return -1;
}
// Checking if the sum of all elements
// is 0 or not. As the whole array can
// also be a subarray.
int sum=0;
int k;
for(k=0;k<n;k++)
{
sum+=arr[k];
}
if(sum==0)
return n;
int prefixSum = 0, suffixSum = 0;
int i = 0, j = n - 1;
// Iterate till there is one element in the
// array
while (i <= j) {
// If prefix sum is less or equal then
// add it in the prefix sum and
// increment i
if (prefixSum <= suffixSum) {
prefixSum += arr[i];
i++;
}
// If suffix sum is less than add it in
// the suffix sum and decrement j
else if (prefixSum > suffixSum) {
suffixSum += arr[j];
j--;
}
// Check if both are equal or not? if they
// are then make ans = "YES" and break
if (prefixSum == suffixSum) {
return j - i + 1;
}
}
if (prefixSum == suffixSum)
return 0;
// return ans;
return -1;
}
// Driver function
public static void Main()
{
int N = 3;
int[] arr = { 10, 20, 10 };
// Function call
Console.WriteLine(isEqual(N, arr));
}
}
Javascript
<script>
// JavaScript program for the above approach
function isEqual(n, arr)
{
// Base Case
if (n == 1) {
return -1;
}
// Checking if the sum of all elements
// is 0 or not. As the whole array can
// also be a subarray.
let sum=0;
for(let i=0;i<n;i++)
{
sum+=arr[i];
}
if(sum==0)
return n;
let prefixSum = 0, suffixSum = 0;
let i = 0, j = n - 1;
// We are assuming that the ans is No
let ans = -1;
// Iterate till there is one element in the
// array
while (i <= j) {
// If prefix sum is less or equal then
// add it in the prefix sum and
// increment i
if (prefixSum <= suffixSum) {
prefixSum += arr[i];
i++;
}
// If suffix sum is less than add it in
// the suffix sum and decrement j
else if (prefixSum > suffixSum) {
suffixSum += arr[j];
j--;
}
// Check if both are equal or not? if they
// are then make ans = "YES" and break
if (prefixSum == suffixSum) {
return j - i + 1;
}
}
if (prefixSum == suffixSum)
return 0;
// return ans;
return -1;
}
// Driver function
let N = 3;
let arr = [10, 20, 10];
// Function call
document.write(isEqual(N, arr) + "<br>");
</script>
Producción
1
Complejidad temporal: O(N)
Espacio auxiliar: O(1)