Shuffling Parities | CodeChef Solution

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

Task

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 B_i = (A_i + 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 A₁, A₂, . . . ,A_N.

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 ≤ 10⁴
• 1 ≤ N ≤ 10⁵
• 1 ≤ A_i ≤ 10⁹
• Sum of N over all test cases does not exceed 3 ⋅ 10⁵.

Subtasks

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

C++

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.