EVENSUM1 - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Given an array A, is it possible to remove exactly one element from it such that the sum of the remaining elements is even?

EXPLANATION:

A solution in \mathcal{O}(N^2) is to try removing each element and recomputing the sum of the remaining ones; and checking if that’s even.

It’s possible to optimize this to \mathcal{O}(N) time as well.

To do this, first compute S = A_1 + A_2 + \ldots + A_N, and then notice that the sum after removing A_i is equal to exactly (S - A_i).
So, we only need to check if any value of (S - A_i) is even.
This is equivalent to checking if S and A_i have the same parity.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    ans = 'No'
    s = sum(a)
    for i in range(n):
        if s%2 == a[i]%2:
            ans = 'Yes'
    print(ans)