PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author: Hriday
Tester: Rahul Dugar
Editorialist: Mohammed Ehab
DIFFICULTY:
SIMPLE
PREREQUISITES:
None
PROBLEM:
Given an array a, in each operation, you can pick any value and increase it by 1. What’s the minimum number of operations you need to make the difference between any 2 elements even?
QUICK EXPLANATION:
The answer is the minimum between the number of even elements and the number of odd elements.
EXPLANATION:
If there’s an even element and an odd element, their difference is odd. Hence, either all the elements must be even, or all the elements must be odd. In one operation, you can change the parity of one element, and your goal is to either make all the odd elements even, or make all the even elements odd, so the answer is just whichever smallest.
SOLUTIONS:
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while (t--)
{
int n,o=0;
scanf("%d",&n);
for (int i=0;i<n;i++)
{
int a;
scanf("%d",&a);
o+=a%2;
}
printf("%d\n",min(o,n-o));
//o is the number of odd elements, so n-o is the number of even elements
}
}