Dada una array arr[] de longitud N , la tarea es encontrar el recuento de pares de índices (i, j) ( indexación basada en 0 ) tal que el prefijo sum of the subarray {arr[0], … arr[i] } es igual a la suma del sufijo del subarreglo {arr[N – 1], …, arr[j]} ( 0 ≤ i, j < N).
Ejemplos:
Entrada: arr[] = {1, 2, 1, 1}
Salida: 3
Explicación:
Los 3 posibles pares de índices son los siguientes:
- Par {0, 3}: Prefijo Suma del subarreglo {arr[0]} = 1. Sufijo Suma del subarreglo {arr[3]} = 1.
- Par {2, 1}: Prefijo Suma de subarreglo {arr[0], .. arr[2]} = 4. Sufijo Suma de subarreglo {arr[3], …, arr[1]} = 4.
- Par {3, 0}: Prefijo Suma de subarreglo {arr[0], .. arr[3]} = 5. Sufijo Suma de subarreglo {arr[3], …, arr[0]} = 5.
Entrada: arr[] = {1, 0, -1}
Salida: 1
Enfoque: La idea es usar Hashing para resolver este problema. Siga los pasos a continuación para resolver el problema:
- Recorra la array arr[] y calcule la suma de prefijos para todos los índices de la array y almacene sus frecuencias en un HashMap .
- Recorra la array en sentido inverso y siga calculando la suma de sufijos hasta cada índice de array.
- Por cada suma de sufijo obtenida, verifique si está presente en el Mapa o no . Si se determina que es cierto, aumente la cuenta en 1 .
- Imprime el conteo obtenido.
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 find the count of
// index pairs having equal
// prefix and suffix sums
void countPairs(int* arr, int n)
{
// Maps indices with prefix sums
unordered_map<int, int> mp1;
int sum = 0;
// Traverse the array
for (int i = 0; i < n; i++) {
// Update prefix sum
sum += arr[i];
// Update frequency in Map
mp1[sum] += 1;
}
sum = 0;
int ans = 0;
// Traverse the array in reverse
for (int i = n - 1; i >= 0; i--) {
// Update suffix sum
sum += arr[i];
// Check if any prefix sum of
// equal value exists or not
if (mp1.find(sum) != mp1.end()) {
ans += mp1[sum];
}
}
// Print the obtained count
cout << ans;
}
// Driver code
int main()
{
// Given array
int arr[] = { 1, 2, 1, 1 };
// Given size
int n = sizeof(arr)
/ sizeof(arr[0]);
// Function Call
countPairs(arr, n);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to find the count of
// index pairs having equal
// prefix and suffix sums
static void countPairs(int []arr, int n)
{
// Maps indices with prefix sums
HashMap<Integer,Integer> mp1 = new HashMap<Integer,Integer>();
int sum = 0;
// Traverse the array
for (int i = 0; i < n; i++)
{
// Update prefix sum
sum += arr[i];
// Update frequency in Map
if(mp1.containsKey(sum)){
mp1.put(sum, mp1.get(sum)+1);
}
else{
mp1.put(sum, 1);
}
}
sum = 0;
int ans = 0;
// Traverse the array in reverse
for (int i = n - 1; i >= 0; i--)
{
// Update suffix sum
sum += arr[i];
// Check if any prefix sum of
// equal value exists or not
if (mp1.containsKey(sum))
{
ans += mp1.get(sum);
}
}
// Print the obtained count
System.out.print(ans);
}
// Driver code
public static void main(String[] args)
{
// Given array
int arr[] = { 1, 2, 1, 1 };
// Given size
int n = arr.length;
// Function Call
countPairs(arr, n);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach
# Function to find the count of
# index pairs having equal
# prefix and suffix sums
def countPairs(arr, n):
# Maps indices with prefix sums
mp1 = {}
sum = 0
# Traverse the array
for i in range(n):
# Update prefix sum
sum += arr[i]
# Update frequency in Map
mp1[sum] = mp1.get(sum, 0) + 1
sum = 0
ans = 0
# Traverse the array in reverse
for i in range(n - 1, -1, -1):
# Update suffix sum
sum += arr[i]
# Check if any prefix sum of
# equal value exists or not
if (sum in mp1):
ans += mp1[sum]
# Print the obtained count
print (ans)
# Driver code
if __name__ == '__main__':
# Given array
arr = [ 1, 2, 1, 1 ]
# Given size
n = len(arr)
# Function Call
countPairs(arr, n)
# This code is contributed by mohit kumar 29
C#
// C# code for above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the count of
// index pairs having equal
// prefix and suffix sums
static void countPairs(int[] arr, int n)
{
// Maps indices with prefix sums
Dictionary<int, int> mp1 = new Dictionary<int, int>();
int sum = 0;
// Traverse the array
for (int i = 0; i < n; i++)
{
// Update prefix sum
sum += arr[i];
// Update frequency in Map
if(mp1.ContainsKey(sum))
{
mp1.Add(sum, mp1[sum] + 1);
}
else{
mp1.Add(sum, 1);
}
}
sum = 0;
int ans = 0;
// Traverse the array in reverse
for (int i = n - 1; i >= 0; i--)
{
// Update suffix sum
sum += arr[i];
// Check if any prefix sum of
// equal value exists or not
if (mp1.ContainsKey(sum))
{
ans += mp1[sum];
}
}
// Print the obtained count
Console.Write(ans);
}
// Driver code
static public void Main ()
{
// Given array
int[] arr = { 1, 2, 1, 1 };
// Given size
int n = arr.Length;
// Function Call
countPairs(arr, n);
}
}
// This code is contributed by offbeat
Javascript
<script>
// Javascript program for the above approach
// Function to find the count of
// index pairs having equal
// prefix and suffix sums
function countPairs(arr, n)
{
// Maps indices with prefix sums
let mp1 = new Map();
let sum = 0;
// Traverse the array
for(let i = 0; i < n; i++)
{
// Update prefix sum
sum += arr[i];
// Update frequency in Map
if (mp1.has(sum))
{
mp1.set(sum, mp1.get(sum) + 1);
}
else
{
mp1.set(sum, 1)
}
}
sum = 0;
let ans = 0;
// Traverse the array in reverse
for(let i = n - 1; i >= 0; i--)
{
// Update suffix sum
sum += arr[i];
// Check if any prefix sum of
// equal value exists or not
if (mp1.has(sum))
{
ans += mp1.get(sum);
}
}
// Print the obtained count
document.write(ans);
}
// Driver code
// Given array
let arr = [ 1, 2, 1, 1 ];
// Given size
let n = arr.length
// Function Call
countPairs(arr, n);
// This code is contributed by gfgking
</script>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por AmanGupta65 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA