5.1 ⚖️🔢 Parity Unification: Even and Odd Harmony 🔄💡
In a realm where numbers are split between two factions—those with even parity and those with odd parity—a quest for unity begins! Your task is to bring harmony by making all the numbers in an array a of n positive integers share the same parity.
You have a special power: whenever you find two numbers with different parity (one even, one odd), you can combine their strengths by replacing the smaller number with the sum of the two. Your mission is to figure out the minimum number of operations needed to make all elements in the array have the same parity.
Constraints
Input Format
The first line contains a single integer t — the number of test cases.
The first line of each test case contains a single integer n
The second line contains n integers a1,a2,a3….an - the elements of array a
Output Format
For each test case, output a single integer — the minimum number of operations required.
Example 1
Input:
7
5
1 3 5 7 9
4
4 4 4 4
3
2 3 4
4
3 2 2 8
6
4 3 6 1 2 1
6
3 6 1 2 1 2
5
999999996 999999997 999999998 999999999 1000000000
Output:
0
0
2
4
3
3
3
Explanation:
Example is self explanatory
Log In to solve the Question