Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #https://www.hackerearth.com/practice/algorithms/searching/linear-search/practice-problems/algorithm/equal-parity-zeros-25eb4114/
- import collections, heapq, itertools, math
- groupby = itertools.groupby
- rs = lambda: input()
- ri = lambda: int(input())
- rmi = lambda: map(int, input().split())
- ra = lambda: [int(x) for x in input().split()]
- pa = lambda x: print (" ".join(map(str, x)))
- def solve():
- sum_odd, sum_even = 0, 0
- for i in range(n):
- if i % 2 == 0:
- sum_even += a[i]
- else:
- sum_odd += a[i]
- target = sum_even - sum_odd
- if target % 2 != 0: return False
- target = target // 2
- cur_sum = 0
- seen = {0}
- for i in range(len(a)):
- if i % 2 == 1:
- a[i] = -a[i] #flip val at odd index
- cur_sum += a[i] #caculate prefix sum
- if cur_sum - target in seen:
- return True
- seen.add(cur_sum)
- return False
- for t in range(ri()):
- n = ri()
- a = ra()
- print('YES' if solve() else 'NO')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement