# REC15A - Editorial

Setter: Shubham
Tester: Sayan Pal
Editorialist: Anuj Patel

Cakewalk

None

### PROBLEM:

We are given an array in which all the elements are unique. Our aim is to make all the elements of that array equal in minimum time if we can choose an odd number and add or subtract in any one element in one second.

### KEY IDEA:

• odd+odd=even
• odd+2*odd=odd
• even+odd=odd
• even+2*odd=even

### EXPLANATION:

From above observations we can come to the conclusion that we need one second to flip parity and two seconds to change any number to another number of the same parity (remember array does not consist of duplicate elements).

Clearly,

if(odd>even)
res=2*(even-1)+odd
else
res=2*(odd-1)+even


### CORNER CASE:

If the array consists of elements with the same parity
Two possible ways:

1. Convert all element to any one element in the array
res=2*(n-1).
2. Flip parity of all the elements.
res=n

If we compare 2*(n-1) and n then we find out :

if (n \geq 2)
n \leq 2*(n-1)

So, if the array consists of elements with the same parity then the answer will be n.

Note: If the length of the array is 1 then the answer will be 0 (all elements are already equal).

### TIME COMPLEXITY:

O(n) for each test case.

### SOLUTION:

Setter's Solution
#include<bits/stdc++.h>
#define ll long long
using namespace std;

void inline solve()
{
ll n,x,i;
cin>>n;
ll e=0,o=0;
for(i=0;i<n;i++)
{
cin>>x;
if(x%2)
++o;
else
++e;
}
if(n==1)
cout<<0<<'\n';
else if(!o||!e)
cout<<n<<'\n';
else
cout<<min(2*(e-1)+o,2*(o-1)+e)<<'\n';
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin>>t;
while(t--)
{
solve();
}
}

Tester's Solution
t=int(input())
for _ in range(t):
n=int(input())
arr=[int(i) for i in input().split()]
count_odd=0
count_even=0
for i in arr:
if i&1:
count_odd+=1
else:
count_even+=1
if count_odd and count_even:
print(min(2*count_odd+count_even,count_odd+2*count_even)-2)
elif n==1:
print(0)
else:
print(max(count_odd,count_even))


On running my code, I was getting the right answer…but it showed wrong answer when submitted. Can anyone point out my mistake?
Here is my code:
#include
#include
using namespace std;

int main() {
int T,N,ar[1000000000],i=0,m,s[1000],min,j;
cin>>T;
while(T–)
{cin>>N;m=N;
while(N–)
{cin>>ar[i];
i++;
}i=0;
for(i=0;i<m;i++)
{s[i]=0;
for(j=0;j<m;j++)
{
if(j!=i)
{if(abs(ar[j]-ar[i])%2==0)
s[i]+=2;
else
s[i]+=1;

    }
else
continue;
}

}
min=s[0];
for(i=0;i<m;i++)
{if(s[i]<min)
min=s[i];}
cout<<min<<endl;
}
return 0;


}

First
Try to format your code properly as your current code is unreadable.

Run Time Error
Remove array of length 1e9 as it will give RTE. We don't need it either.

TLE
Expected time complexity is O(n) . But time complexity of your code is O(n*n)
that will eventually give TLE.

Wrong Logic
Logically it is incorrect.
Try this case
1
5
1 3 5 7 9