PROBLEM LINK:
DIFFICULTY:
CakeWalk
PREREQUISITES:
None at all
PROBLEM:
Find the minimum number of actions needed such that she can make the array A beautiful, or say that this is not possible. Note that array indices start from zero.
See the problem here
EXPLANATION:
We split all the positions in which the parity of the index does not match with the parity of the element into two arrays.
If there is an odd number in the even index, add this index to the e array. Otherwise, if there is an even number in the odd index, add this index to the o array. Note that if the sizes of the o and e arrays are not equal, then there is no answer. Otherwise, the array a can be made Beautiful by doing exactly |o| operations by simply swapping all the elements in the o and e arrays.
SOLUTIONS:
Solution 1
#include <iostream>
using namespace std;
#define ll long long
void solve()
{
int n;
cin >> n;
int a[n];
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
int count1 = 0, count2 = 0;
for (int i = 0; i < n; i++)
{
if (i % 2 == 0 && a[i] % 2 != 0)
{
count1++;
}
else if (i % 2 != 0 && a[i] % 2 != 1)
{
count2++;
}
}
if (count1 == count2)
{
cout << count1 << endl;
}
else
{
cout << -1 << endl;
}
}
int main()
{
int t;
cin >> t;
while (t--)
{
solve();
}
return 0;
}