← All coding problems
Zero-Sum Subarray
easyArrays & Prefix Sums+10 XPTime limit 2s
Does the array contain a non-empty contiguous subarray whose elements add up to exactly 0?
Input:
- line 1:
n - line 2:
nintegers
Output: true or false.
Constraints: 1 ≤ n ≤ 10⁵, −10⁹ ≤ a[i] ≤ 10⁹ (prefix sums need 64-bit integers).
Think about it: a subarray a[l..r] sums to zero exactly when the prefix sum before l equals the prefix sum at r. Walk through the array keeping a hash set of prefix sums seen so far (start with 0). A repeat means "yes".
Sample input 1
5 4 2 -3 1 6
Sample output 1
true
Sample input 2
3 1 2 3
Sample output 2
false
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).