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