# Shuffling Parities Solution September Challenge 2021

## Shuffling Parities Codechef Solution

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)mod2, 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)mod2,(1+2)mod2,(3+3)mod2]=[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)mod2,(5+2)mod2,(4+3)mod2]=[1,1,1]. So the sum of integers of array B is 3 .

### SOLUTION

Program C: Shuffling Parities Codechef Solution in C

``````#include <stdio.h>
int main(void) {
int tc;
scanf("%d",&tc);
for(int z=0;z<tc;z++){
int n;
scanf("%d",&n);
int arr[n],sum=0,x,y,ev=0,odd=0;
if(n%2==0){
x=n/2;
y=n/2;
}
else{
x=(n/2)+1;
y=n/2;
}
for(int i=0;i<n;i++){
scanf("%d",&arr[i]);
if(arr[i]%2==0){
ev++;
}
else{
odd++;
}
}
if(ev>x){
sum+=x;
}
else{
sum+=ev;
}
if(odd>y){
sum+=y;
}
else{
sum+=odd;
}
printf("%d\n",sum);
}
return 0;
}``````

Program C++: Shuffling Parities Codechef Solution in C++

``````#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
int t;
cin>>t;
while(t--)
{
int n,c1=0,c2=0,c3=0,c4=0;
cin>>n;
int a[n+5],b[n+5];

for(int i=1;i<=n;i++)
{
cin>>a[i];

if(i%2==0)  //even of index
c1++;
if(i%2!=0) //odd of index
c2++;
if(a[i]%2==0) //even of array
c3++;
if(a[i]%2!=0) //odd of array
c4++;

}

cout<<min(c1,c4)+min(c2,c3)<<endl;
}
}``````

Program Java: Shuffling Parities Codechef Solution in Java

``````import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
try{
Scanner scr= new Scanner(System.in);
int t= scr.nextInt();
while(t-->0){
int n= scr.nextInt();
double temp= n;
int oddindex=(int) Math.ceil(temp/2);

int evenindex=n-oddindex;
int ar[]= new int[n];
int arreven=0;
int arrodd=0;
for(int i=0;i<n;i++){
ar[i]= scr.nextInt();
if(ar[i]%2==0){
arreven+=1;
}
else{
arrodd+=1;
}
}
int count=Math.min(oddindex,arreven)+Math.min(evenindex,arrodd);
System.out.println(count);
}
}catch(Exception e){
return;
}
}
}``````

Program Python: Shuffling Parities Codechef Solution in Python

``````for _ in range (int(input())):
n=int(input())
l=list(map(int,input().split()))
flag=tmp=0
for i in l:
if(i%2==1):
flag+=1
else:
tmp+=1
tt=min(flag,n//2 )+ min(tmp,(n+1)//2)
print(tt)``````

## September Long Challenge 2021 Solution

### 3 thoughts on “Shuffling Parities Solution September Challenge 2021”

1. This Gives Runtime Error