Count Subarrays with Equal Prefix Sums
Given an array of N integers, find the number of pairs of indices (i, j) such that 0 <= i < j < N and the prefix sum up to index i-1 is equal to the prefix sum up to index j-1. The prefix sum up to index k is defined as the sum of elements from index 0 to k (inclusive). The prefix sum up to index -1 (before the first element) is considered to be 0.
Input
The first line contains a single integer N, the size of the array. The second line contains N space-separated integers, representing the elements of the array.
Output
A single integer representing the total count of pairs (i, j) satisfying the condition.
Constraints
1 <= N <= 200000. The array elements are integers between -10^9 and 10^9.
Example 1
5 1 2 -1 -2 3
2
Prefix sums (including initial 0): [0, 1, 3, 2, 0, 3]. Pairs with equal sums: (0, 3) for value 0, (1, 4) for value 3. Count = 2.
Example 2
3 0 0 0
6
Prefix sums: [0, 0, 0, 0]. Pairs: (0,1), (0,2), (0,3), (1,2), (1,3), (2,3). Count = 6.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
5 1 2 -1 -2 3
3 0 0 0