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

You are given an array A. Find the minimum number of element changes needed for it to have alternating parities.

EXPLANATION:

The parities of the array must be either

\text{even, odd, even, odd, } \ldots

or

\text{odd, even, odd, even, } \ldots

If we try to make it \text{even, odd, even, odd, } \ldots then the elements at indices 1, 3, 5, \ldots must be even while the elements at indices 2, 4, 6, \ldots must be odd.
Any element that doesn’t satisfy this must be changed; and for each such element, one change is enough since we can always set them to either 1 or 2.

So, it’s easy to count the number of changes needed for a fixed pattern.

Simply do this for both patterns and print the minimum of the two costs.

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()))
    
    ct1, ct2 = 0, 0
    for i in range(n):
        if i%2 == a[i]%2: ct1 += 1
        else: ct2 += 1
    print(min(ct1, ct2))