Given an array arr[] of length N, the task is to find the count of pairs of indices (i, j) (0-based indexing) such that prefix sum of the subarray {arr[0], … arr[i]} is equal to the suffix sum of the subarray {arr[N – 1], …, arr[j]} ( 0 ? i, j < N).
Examples:
Input: arr[] = {1, 2, 1, 1}
Output: 3
Explanation:
The 3 possible pairs of indices are as follows:
- Pair {0, 3}: Prefix Sum of subarray {arr[0]} = 1. Suffix Sum of subarray {arr[3]} = 1.
- Pair {2, 1}: Prefix Sum of subarray {arr[0], .. arr[2]} = 4. Suffix Sum of subarray {arr[3], …, arr[1]} = 4.
- Pair {3, 0}: Prefix Sum of subarray {arr[0], .. arr[3]} = 5. Suffix Sum of subarray {arr[3], …, arr[0]} = 5.
Input: arr[] = {1, 0, -1}
Output: 1
Approach: The idea is to use Hashing to solve this problem. Follow the steps below to solve the problem:
- Traverse the array arr[] and calculate prefix sum for all array indices and store their frequencies in a HashMap.
- Traverse the array in reverse and keep calculating suffix sum up to every array index.
- For every suffix sum obtained, check if it is present in the Map or not. If found to be true, increase count by 1.
- Print the count obtained.
Below is the implementation of the above approach:
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 sumsvoid 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 codeint 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 approachimport 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 sumsdef 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 codeif __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 approachusing 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 sumsfunction 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 arraylet arr = [ 1, 2, 1, 1 ];// Given sizelet n = arr.length// Function CallcountPairs(arr, n);// This code is contributed by gfgking</script> |
Output:
3
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
