Dada una array arr[] de enteros, la tarea es encontrar el número de índices hasta los cuales la suma de prefijos y la suma de sufijos son iguales.
Ejemplo:
Entrada: arr = [9, 0, 0, -1, 11, -1]
Salida: 2
Explicación: Los índices hasta los cuales la suma de prefijos y sufijos son iguales se dan a continuación:
En el índice 1, la suma de prefijos y sufijos es 9
En el índice 2 suma de prefijos y sufijos son 9Entrada: arr = [5, 0, 4, -1, -3, 0, 2, -2, 0, 3, 2]
Salida: 3
Explicación: Los subarreglos de prefijos y los subarreglos de sufijos con igual suma se dan a continuación:
En el índice 1 la suma de prefijo y sufijo es 5
En el índice 5 la suma de prefijo y sufijo es 5
En el índice 8 la suma de prefijo y sufijo es 5
Enfoque ingenuo: el problema dado se puede resolver recorriendo la array arr de izquierda a derecha y calculando la suma del prefijo hasta ese índice, luego iterando la array arr de derecha a izquierda y calculando la suma del sufijo y luego verificando si el prefijo y la suma del sufijo son iguales.
Complejidad del tiempo: O(N^2)
Enfoque: el enfoque anterior se puede optimizar iterando la array arr dos veces. La idea es calcular previamente la suma del sufijo como la suma total del subarreglo. Luego itere la array por segunda vez para calcular la suma de prefijos en cada índice, luego compare las sumas de prefijos y sufijos y actualice la suma de sufijos. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable res a cero para calcular la respuesta
- Inicialice una variable sufSum para almacenar la suma del sufijo
- Inicialice una variable preSum para almacenar la suma del prefijo
- Recorra la array arr y agregue cada elemento arr[i] a sufSum
- Itere la array arr nuevamente en cada iteración:
- Agrega el elemento actual arr[i] en preSum
- Si preSum y sufSum son iguales, incremente el valor de res en 1
- Resta el elemento actual arr[i] de sufSum
- Devuelve la respuesta almacenada en res
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate number of
// equal prefix and suffix sums
// till the same indices
int equalSumPreSuf(int arr[], int n)
{
// Initialize a variable
// to store the result
int res = 0;
// Initialize variables to
// calculate prefix and suffix sums
int preSum = 0, sufSum = 0;
// Length of array arr
int len = n;
// Traverse the array from right to left
for (int i = len - 1; i >= 0; i--)
{
// Add the current element
// into sufSum
sufSum += arr[i];
}
// Iterate the array from left to right
for (int i = 0; i < len; i++)
{
// Add the current element
// into preSum
preSum += arr[i];
// If prefix sum is equal to
// suffix sum then increment res by 1
if (preSum == sufSum)
{
// Increment the result
res++;
}
// Subtract the value of current
// element arr[i] from suffix sum
sufSum -= arr[i];
}
// Return the answer
return res;
}
// Driver code
int main()
{
// Initialize the array
int arr[] = {5, 0, 4, -1, -3, 0,
2, -2, 0, 3, 2};
int n = sizeof(arr) / sizeof(arr[0]);
// Call the function and
// print its result
cout << (equalSumPreSuf(arr, n));
}
// This code is contributed by Potta Lokesh
Java
// Java implementation for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to calculate number of
// equal prefix and suffix sums
// till the same indices
public static int equalSumPreSuf(int[] arr)
{
// Initialize a variable
// to store the result
int res = 0;
// Initialize variables to
// calculate prefix and suffix sums
int preSum = 0, sufSum = 0;
// Length of array arr
int len = arr.length;
// Traverse the array from right to left
for (int i = len - 1; i >= 0; i--) {
// Add the current element
// into sufSum
sufSum += arr[i];
}
// Iterate the array from left to right
for (int i = 0; i < len; i++) {
// Add the current element
// into preSum
preSum += arr[i];
// If prefix sum is equal to
// suffix sum then increment res by 1
if (preSum == sufSum) {
// Increment the result
res++;
}
// Subtract the value of current
// element arr[i] from suffix sum
sufSum -= arr[i];
}
// Return the answer
return res;
}
// Driver code
public static void main(String[] args)
{
// Initialize the array
int[] arr = { 5, 0, 4, -1, -3, 0,
2, -2, 0, 3, 2 };
// Call the function and
// print its result
System.out.println(equalSumPreSuf(arr));
}
}
Python3
# Python implementation for the above approach # Function to calculate number of # equal prefix and suffix sums # till the same indices from builtins import range def equalSumPreSuf(arr): # Initialize a variable # to store the result res = 0; # Initialize variables to # calculate prefix and suffix sums preSum = 0; sufSum = 0; # Length of array arr length = len(arr); # Traverse the array from right to left for i in range(length - 1,-1,-1): # Add the current element # into sufSum sufSum += arr[i]; # Iterate the array from left to right for i in range(length): # Add the current element # into preSum preSum += arr[i]; # If prefix sum is equal to # suffix sum then increment res by 1 if (preSum == sufSum): # Increment the result res += 1; # Subtract the value of current # element arr[i] from suffix sum sufSum -= arr[i]; # Return the answer return res; # Driver code if __name__ == '__main__': # Initialize the array arr = [5, 0, 4, -1, -3, 0, 2, -2, 0, 3, 2]; # Call the function and # prits result print(equalSumPreSuf(arr)); # This code is contributed by 29AjayKumar
C#
// C# implementation for the above approach
using System;
class GFG
{
// Function to calculate number of
// equal prefix and suffix sums
// till the same indices
static int equalSumPreSuf(int[] arr)
{
// Initialize a variable
// to store the result
int res = 0;
// Initialize variables to
// calculate prefix and suffix sums
int preSum = 0, sufSum = 0;
// Length of array arr
int len = arr.Length;
// Traverse the array from right to left
for (int i = len - 1; i >= 0; i--) {
// Add the current element
// into sufSum
sufSum += arr[i];
}
// Iterate the array from left to right
for (int i = 0; i < len; i++) {
// Add the current element
// into preSum
preSum += arr[i];
// If prefix sum is equal to
// suffix sum then increment res by 1
if (preSum == sufSum) {
// Increment the result
res++;
}
// Subtract the value of current
// element arr[i] from suffix sum
sufSum -= arr[i];
}
// Return the answer
return res;
}
// Driver code
public static void Main()
{
// Initialize the array
int[] arr = { 5, 0, 4, -1, -3, 0,
2, -2, 0, 3, 2 };
// Call the function and
// print its result
Console.Write(equalSumPreSuf(arr));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// Javascript code for the above approach
// Function to calculate number of
// equal prefix and suffix sums
// till the same indices
function equalSumPreSuf(arr, n)
{
// Initialize a variable
// to store the result
let res = 0;
// Initialize variables to
// calculate prefix and suffix sums
let preSum = 0, sufSum = 0;
// Length of array arr
let len = n;
// Traverse the array from right to left
for (let i = len - 1; i >= 0; i--)
{
// Add the current element
// into sufSum
sufSum += arr[i];
}
// Iterate the array from left to right
for (let i = 0; i < len; i++)
{
// Add the current element
// into preSum
preSum += arr[i];
// If prefix sum is equal to
// suffix sum then increment res by 1
if (preSum == sufSum)
{
// Increment the result
res++;
}
// Subtract the value of current
// element arr[i] from suffix sum
sufSum -= arr[i];
}
// Return the answer
return res;
}
// Driver code
// Initialize the array
let arr = [5, 0, 4, -1, -3, 0,
2, -2, 0, 3, 2];
let n = arr.length
// Call the function and
// print its result
document.write(equalSumPreSuf(arr, n));
// This code is contributed by Samim Hossain Mondal.
</script>
3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA