Advertisement
whiteshark05

Hacker Rank

Jan 1st, 2023 (edited)
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.02 KB | Software | 0 0
  1. #https://www.hackerearth.com/practice/algorithms/searching/linear-search/practice-problems/algorithm/equal-parity-zeros-25eb4114/
  2. import collections, heapq, itertools, math
  3. groupby = itertools.groupby
  4. rs  = lambda: input()
  5. ri  = lambda: int(input())
  6. rmi  = lambda: map(int, input().split())
  7. ra = lambda: [int(x) for x in input().split()]
  8. pa = lambda x: print (" ".join(map(str, x)))
  9.  
  10. def solve():
  11.     sum_odd, sum_even = 0, 0
  12.  
  13.     for i in range(n):
  14.         if i % 2 == 0:
  15.             sum_even += a[i]
  16.         else:
  17.             sum_odd += a[i]
  18.     target = sum_even - sum_odd
  19.    
  20.     if target % 2 != 0: return False
  21.     target = target // 2
  22.  
  23.     cur_sum = 0
  24.     seen = {0}
  25.     for i in range(len(a)):
  26.         if i % 2 == 1:
  27.             a[i] = -a[i] #flip val at odd index
  28.         cur_sum += a[i] #caculate prefix sum
  29.         if cur_sum - target in seen:
  30.             return True
  31.         seen.add(cur_sum)
  32.     return False
  33.    
  34. for t in range(ri()):
  35.     n = ri()
  36.     a = ra()
  37.     print('YES' if solve() else 'NO')
Tags: Hacker Rank
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement