Make Them Equal solution codechef

Make Them Equal solution codechef

 

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

Given an array AA of size NN. You can perform the following operation on the array:

  • Choose indices ii and jj (1i,j|A|,ij)(1≤i,j≤|A|,i≠j).
  • Append Ai+AjAi+Aj to the array AA.
  • Remove the ithith and jthjth elements from the array AA.

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.

Make Them Equal solution codechef

  • The first line contains a single integer TT – number of test cases.
  • The first line of each test case contains a single integer NN – the size of the array.
  • The second line of each test case contains NN space-separated integers A1,A2,,ANA1, A2, …, AN.

Output Format

For each test case, print a single integer denoting the minimum number of operations required to make the array good.

Make Them Equal solution codechef

  • 1T1041≤T≤104
  • 1N21051≤N≤2⋅105
  • 0Ai1050≤ Ai≤ 105
  • Sum of NN over all test cases does not exceed 21052⋅105.

Sample Input 1 

2
4
1 2 3 4
5
1 1 1 1 1
[Coding] Make Them Equal solution codechef
1
0

Explanation

Test case 11: In one operation, choose i=1i=1 and j=3j=3. Thus, we remove the elements 11 and 33 from the array and append 1+3=41+3=4 to the array.
The updated array is [2,4,4][2,4,4]. All elements of the updated array are even. Thus, the array is good.

Test case 22: All elements of the array are 11, which is odd. Thus, the array is already good.

Leave a Comment