REC15A - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest

Setter: Shubham
Tester: Sayan Pal
Editorialist: Anuj Patel

DIFFICULTY:

Cakewalk

PREREQUISITES:

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))
2

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;

}

3
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
Expected answer is 5.