# PROBLEM LINK:

Contest Division 1

Contest Division 2

Contest Division 3

Contest Division 4

Setter: Jeevan Mayur Koli

Tester: Abhinav Sharma, Nishank Suresh

Editorialist: Pratiyush Mishra

# DIFFICULTY:

Simple

# PREREQUISITES:

Basic Arithmetic

# PROBLEM:

An array is said to be *good* if all the elements of the array have the **same** parity. For example, the arrays [2, 8] and [9, 1, 3] are *good* while the array [4,5,6] is not *good*.

Given an array A of size N. You can perform the following operation on the array:

- Choose indices i and j (1 \le i, j \le |A|, i \ne j).
- Append A_i + A_j to the array A.
- Remove the i^{th} and j^{th} elements from the array A.

Find the **minimum** number of operations required to make the array *good*.

It is guaranteed that the array can be converted to a *good* array using a finite number of operations.

# EXPLANATION:

For a given array, if the existing number of odd numbers are odd then the resulting good array must have all odd numbers as the last odd number would always exist among the other even numbers. So the minimum chances to get to a point where there are no even numbers left in the array would be to use an odd number and an even number to get an odd number in every step. So, here the minimum steps would be the number of even numbers in the initial array.

If there are even number of odd numbers in the array, then the resuting good array may either have all numbers as odd or even. Let there be O odd numbers and E even numbers in the array. To make a good array of all even numbers, the way with least number of steps would be to add couple of odd numbers and make an even number, resulting in O/2 steps. Whereas, to make a good array with all odd numbers, each even number would be added to an odd number resulting in E steps. So in this case, the minimum steps would be min(O/2 , E).

# TIME COMPLEXITY:

O(N) for each test case as we traverse the array.

# SOLUTION:

Editorialistâ€™s Solution

Setterâ€™s Solution

Tester1â€™s Solution

Tester2â€™s Solution