EVEN ARRAY
You are given an array a[n] of length n which consists of non-negative integers. An array is good if for all i (0≤ i< n) the equality i mod2=a[i] mod2 holds, where xmod2 is the remainder of dividing x by 2.
In one move, we can take any two elements of the array and swap them (these elements are not necessarily adjacent). Find the minimum number of moves in which you can make the array a good, or say that this is not possible. ( question source: codeforces.com)
For example, the arrays [0,5,2,1] and [0,17,0,3] are good, and the array [2,4,6,7] is bad, because for i=1, the parities of i and a[i] are different: imod2=1mod2=1, but a[i]mod2=4mod2=0.
Input format :
t (no of test cases)
n (size of array)
a[n] (array elements)
output
minimum number of moves to make a good array, if not possible print -1.
CODE: ( This code is implemented using stack)
#include <iostream>
#include<stack>
using namespace std;
int main()
{
int t,i;
cin>>t;
for(i=0;i<t;i++)
{
int n,j,p=0,q=0;
stack<int>s1,s2;
cin>>n;
int a[n];
for(j=0;j<n;j++)
{
cin>>a[j];
}
for(j=0;j<n;j++)
{
if(j%2!=a[j]%2)
{
if(j%2==0)
{
s1.push(j);
p++;
}
else
{
s2.push(j);
q++;
}
}
}
int c=0;
if(s1.empty() && s2.empty())
cout<<0<<endl;
else if (p!=q)
cout<<-1<<endl;
else
{
while(!s1.empty() && !s2.empty())
{
c++;
s1.pop();
s2.pop();
}
cout<<c<<endl;
}
}
return 0;
}
0 Comments