30 Days of Code [Day 20]

02 Sep 2021

QUESTION : Shuffling Parities Problem Code: SHUFFLIN

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double
#define vi vector<int>
#define vvi vector<vi>
#define vl vector<long>
#define vvl vector<vl>
#define pii pair<int, int>
#define pll pair<long, long>

#define endl "\n"
#define fo(i,s,n) for(int i=s;i<n;++i)
#define of(i,s,n) for(int i=s-1;i>=n;--i)
#define printv(v) for(auto &it : v){cout<<it<<" ";}cout<<endl;
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define fv(V) for( auto &it : V )

const int MOD = 1e9+7;

void solve()
{
    long n;
    cin>>n;
    int oc = 0, ec = 0;
    fo(i,0,n){
        ll inp;
        cin>>inp;
        if(inp & 1) oc++;
        else ec++;
    }
    int res = 0;
    if(n & 1){
        if(ec >= (n/2)+1) res += (n/2)+1;
        else res += ec;
    }
    else{
        if(ec >= (n/2)) res += n/2;
        else res += ec;
    }
    if(oc >= n/2) res += n/2;
    else res += oc;
    cout<<res<<endl;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    ll T=1;
    cin>>T;
    while(T--) solve();
    return 0;
}