Count Distinct Prefix Sums
MediumPractice library · +20 XPmathprefix sumshashing
Given a sequence of N integers a_1, a_2, ..., a_N, compute the number of distinct values that appear in the sequence of prefix sums P_0, P_1, ..., P_N, where P_0 = 0 and P_i = a_1 + a_2 + ... + a_i for i >= 1.
Input
The first line contains an integer N (1 <= N <= 200000). The second line contains N integers a_1, a_2, ..., a_N (-10^9 <= a_i <= 10^9).
Output
Print a single integer: the number of distinct prefix sums.
Constraints
1 <= N <= 200000 -10^9 <= a_i <= 10^9
Time limit 2 s (native code; slower languages get more)Memory 256 MB11 hidden tests
Example 1
Input
5 1 2 3 4 5
Output
6
Prefix sums are 0, 1, 3, 6, 10, 15. All 6 are distinct.
Example 2
Input
4 1 -1 1 -1
Output
2
Prefix sums are 0, 1, 0, 1, 0. Distinct sums are 0, 1. Count is 2.
Hints
Similar problems
- Count Pairs with Digit Sum Divisible by KMedium
- Subarray Sum MultiplesMedium
- String PartitionMedium
- Two Sum Modulo KMedium
- Count Pairs with Equal Digit ProductMedium
- Subsegment Sum Divisible by KMedium
More topics: Hash Map and Hashing problems, Prefix Sums problems, Math and Number Theory problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
5 1 2 3 4 5
Example 2 input
4 1 -1 1 -1