ODDPREFSUM - 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:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Given an array A, can it be rearranged in such a way that all its prefix sums are odd?

EXPLANATION:

Let’s analyze what an array with all odd prefix sums must look like.

Define P_i = A_1 + A_2 + \ldots + A_i to be the i-th prefix sum of A.
Then,

  • P_1 must be odd.
    P_1 = A_1, which means A_1 must be odd.
  • P_2 must be odd.
    P_2 = A_1 + A_2, and A_1 is already odd. So, for P_2 to be odd, A_2 must be even.
  • P_3 must be odd.
    P_3 = A_1 + A_2 + A_3 = P_2 + A_3.
    P_2 is already odd, so again A_3 must be even.
  • In general, for any i \gt 1, we have P_i = P_{i-1} + A_i.
    For both P_i and P_{i-1} to be odd, A_i must be even.

So, the only possible way all prefix sums can be odd, is if A_1 is odd and then all of A_2, A_3, \ldots, A_N are even.

Thus, if A contains exactly one odd number, a valid rearrangement exists - by placing this single odd number at the beginning and everything else afterwards.
Otherwise, no rearrangement can exist.

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()))
    
    odds = 0
    for x in a:
        if x%2 == 1: odds += 1
    
    print('Yes' if odds == 1 else 'No')