Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Hashing & Two Pointers

Zero Sum Subarray

Medium · Hashing & Two Pointers · Asked at Amazon, Microsoft, Paytm

Print YES if there is a non-empty contiguous subarray with sum 0, otherwise NO.

Input

First line: n. Second line: n integers.

Output

YES or NO.

Constraints

If the same prefix sum appears twice (or a prefix sum is 0), the part between them sums to 0.

Example 1

Input

5
4 2 -3 1 6

Output

YES

Example 2

Input

5
5 3 1 2 7

Output

NO

Hints

  1. sum(a[i+1..j]) = prefix[j] − prefix[i].
  2. So a zero-sum subarray exists exactly when some prefix sum repeats (count the empty prefix 0 as already seen).

Approach

Keep a hash set of the prefix sums seen so far, starting with 0 for the empty prefix. Add each element to the running sum. If the sum is already in the set, the elements since that earlier point add up to 0, so answer YES. Otherwise insert it.

Complexity: O(n) average time · O(n) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    unordered_set<long long> seen = {0};
    long long prefix = 0;
    bool found = false;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        prefix += x;
        if (!seen.insert(prefix).second) found = true;
    }
    cout << (found ? "YES" : "NO") << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
seen, prefix, found = {0}, 0, False
for x in data[1 : data[0] + 1]:
    prefix += x
    if prefix in seen:
        found = True
        break
    seen.add(prefix)
print("YES" if found else "NO")

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Set<Long> seen = new HashSet<>();
        seen.add(0L);
        long prefix = 0;
        boolean found = false;
        for (int i = 0; i < n; i++) {
            prefix += sc.nextLong();
            if (!seen.add(prefix)) found = true;
        }
        System.out.println(found ? "YES" : "NO");
    }
}

Solve Zero Sum Subarray online · All practice problems