ALLEV - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

You’re given an array A.
It can be modified as follows:

  • Add A_N to A_{N-1}, then delete A_N from A.

Is it possible to make all remaining elements of A be even?

EXPLANATION:

Performing the operation N-1 times will result in us having a single integer, at which point no more operations can be performed.

This leads to a simple, direct solution: just keep trying to perform the given operation, and after each one, check if every remaining element is even.
The complexity of this is \mathcal{O}(N^2).

For a smarter solution, observe that the total sum of the elements is not changed by the operation.
So,

  • If the total sum is even, the answer is Yes - we can keep performing the operation till there’s one element left, which will be the sum of everything and hence even.
  • If the total sum is odd, the answer is No - because if we were able to have only even numbers, their sum must be even too; which is impossible when the total sum is odd.

This gives a solution in \mathcal{O}(N): just check if the sum of A is even or odd.

TIME COMPLEXITY:

\mathcal{O}(N) or \mathcal{O}(N^2) per testcase.

CODE:

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