# Shuffling Parities | CodeChef Solution

Hello coders, today we are going to solve Shuffling Parities CodeChef Solution whose Problem Code is SHUFFLIN.

Chef is given an array A consisting of N positive integers. Chef shuffles the array A and creates a new array B of length N, where Bi = (Ai + i) mod 2, for each i (1 ≤ i N).

Find the maximum possible sum of integers of the array B, if Chef shuffles the array A optimally.

## Input Format

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• Each test case contains two lines of input.
• The first line of each test case contains an integer N.
• The second line of each test case contains N space-separated integers A1, A2, . . . ,AN.

## Output Format

For each test case, print a single line containing one integer – the maximum sum of integers of the array B.

## Constraints

• 1 ≤ T ≤ 104
• 1 ≤ N ≤ 105
• 1 ≤ Ai ≤ 109
• Sum of N over all test cases does not exceed 3 ⋅ 105.

Subtask #1 (100 points): Original constraints

Sample Input 1

`````` 3
3
1 2 3
3
2 4 5
2
2 4
``````

Sample Output 1

`````` 2
3
1
``````

Explanation

Test case 1: One of the optimal ways to shuffle the array A is [2, 1, 3]. Then the array B = [(2 + 1) mod 2,(1 + 2) mod 2,(3 + 3) mod 2] = [1, 1, 0]. So the sum of integers of array B is 2. There is no other possible way to shuffle array A such that the sum of integers of array B becomes greater than 2.

Test case 2: One of the optimal ways shuffle the array A is [2, 5, 4]. Then the array B = [(2 + 1) mod 2,(5 + 2) mod 2,(4 + 3) mod 2] = [1, 1, 1]. So the sum of integers of array B is 3.

## Solution – Shuffling Parities

### Python

```# cook your dish here
import math
T = int(input())
for i in range(T):
N = int(input())
ar = list(map(int, input().split()))

count_odd = 0
count_even = 0

for num in ar:
if num % 2:
count_odd += 1
else:
count_even += 1

num_odd = math.ceil(N/2)
num_even = math.floor(N/2)

maximum_value = min(count_odd, num_even) + min(count_even, num_odd)

print(maximum_value)```

### Java

Disclaimer: The above Problem (Shuffling Parities) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.