 # EVEQODD - Editorial

Setter: Rudro Debnath
Tester: Takuki Kurokawa
Editorialist: Yash Kulkarni

1363

Basic Math

# PROBLEM:

You are given an array containing \texttt{2*N} integers.

You can do only the below operation any number of times:

• Choose any a[i] such that a[i] is even and divide it by 2.
• Choose any a[i] and multiply it by 2.

Find the minimum number of operation required to make the count of even and odd numbers equal.

# EXPLANATION:

Let us first know the minimum number of operations required to change the parity of any element in the given array:

• The minimum number of operations required to convert any odd number in the array to an even number is 1 i.e. by using the second operation once.
• Any even number can be represented as C.2^B, where C is odd and B \geq 1. The minimum number of operations required to convert any even number (C.2^B) in the array to an odd number is B i.e. by applying the first operation B times so that the new number os C. There is no point in applying the second operation on an even number.

For an even number X = C.2^B, we can find out B in O(log(X)) time complexity. We will store the B's (for all even numbers in the given array) in an array say D.

Let there be O odd numbers and E ( =2N - O) even numbers in the array. There can be only three possibilities:

• O = E, the answer is zero.
• O > E, we need to change (O - E)/2 odd numbers to even numbers. This will require a minimum of (O - E)/2 operations.
• E > O, we need to change (E - O)/2 even numbers to odd numbers. We will choose the even numbers with the least B's to be changed to odd numbers for the least number of operations. So, the answer is the sum of (E - O)/2 minimum elements in array D.

# TIME COMPLEXITY:

O(Nlog(max(A_i))) + O(NlogN) for each test case.

# SOLUTION:

Setter's solution
``````using namespace std;

int main() {
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
vector<int> a(2 * n);
for (int i = 0; i < 2 * n; i++) {
cin >> a[i];
}
vector<int> p2(2 * n);
for (int i = 0; i < 2 * n; i++) {
while (a[i] % 2 == 0) {
a[i] /= 2;
p2[i]++;
}
}
sort(p2.begin(), p2.end());
int odds = (int) count(p2.begin(), p2.end(), 0);
int ans = 0;
if (odds <= n) {
for (int i = 0; i < n; i++) {
ans += p2[i];
}
} else {
ans = odds - n;
}
cout << ans << endl;
}
return 0;
}
``````
Editorialist's Solution
``````using namespace std;

int main() {
int T;
cin >> T;
while(T--){
int n;
cin >> n;
n*=2;
vector<int>a(n);
int e=0,o=0;
vector<int>make_o;
for(int i=0;i<n;i++){
cin >> a[i];
if(a[i]%2)o++;
else{
e++;
int x=0;
while(a[i]%2==0){
x++;
a[i]/=2;
}
make_o.push_back(x);
}
}
sort(make_o.begin(),make_o.end());
if(o>=e)cout << (o-e)/2 << endl;
else{
int ans=0;
for(int i=0;i<(e-o)/2;i++)ans+=make_o[i];
cout << ans << endl;
}
}
return 0;
}
``````

are we taking 0 as an odd number?

what is this???

the input element is 2* 100000 but how we will get the answer in 2900000

1 Like

It is mentioned that , n <= 1e5 ; if we multiply it with 2 , we should store it in long , not int !

0 is not included in constraint

0 will never come as an input nor as quotient when divided by 2

can’t we just directly n-e(o>e) and n-o(e>o) it gives wrong answer else 0 , it gives wrong answer

https://www.codechef.com/viewsolution/67986031

this is my solution for the Question. I thought that if count of odd>even(n-even);
even>odd(n-odd) ;else 0 would be the answer but it wasn’t the case and after seeing a bunch of solution i got it if odd>even (then n-even) ;if odd==even (then 0) but if even>odd(then we have to reduce the even element and find the odd)…
In my code i worte reduce function, but one Q i worte n%2==0 what if the even number was 42, and i had to reduce it ? should 42/2 = 21 count as odd? I tried this first
while(n%2==0) || (n%2==1)) {
int moves =0;
while(n%2==0){
n/=2;
moves++;
}
if(n%2==1)
break;
else
continue;
return moves;
}

what was wrong with this code??

#include<bits/stdc++.h>
using namespace std ;
#define ll long long
const ll M = 1e9+7 ;
#define pb push_back ;

void S(){

`````` ll n ; cin >> n ;

if( n == 1 )
{
ll x , y ; cin >> x >> y ;
if( ((x&1) == 0 )  and ((y&1) == 0 ) )
{cout <<"1\n";return;}
if( ((x&1) != 0 )  and ((y&1) != 0 ) )
{cout <<"1\n";return;}
else {cout <<"0\n";return;}

}

ll ct_odd = 0 ;
ll ct_even = 0 ;
``````

// set< ll > odd ;
unordered_set< ll >even ;

`````` for( int i = 0 ; i < (2*n) ; i++ )
{
ll e ; cin >> e ;
//  vec1[i] = e ;
if( (e&1) == 0  ){
ct_even ++ ;
even.insert( e ) ;
}else{
ct_odd++;
//  odd.insert( e ) ;
}
}

if( ct_odd == ct_even ) { cout <<"0\n"; return ; }

if( ct_odd > ct_even ) {
cout << ct_odd - n <<"\n";return;
}

// main yeh hai
vector< ll > count ;
for( auto itr = even.begin() ; itr!=even.end() ; itr++ )
{
ll num = (*itr) ;
ll ct = 0 ;
while( num > 1)
{
num = num / 2 ;
ct++;
if( (num&1) != 0  )break ;
}
count.push_back( ct)  ;
}
``````

// for(auto i : count ) cout << i <<" " ;
sort( count.begin() , count.end() ) ;
ll k = ct_even - n ;
ll i = 0 ;
ll ans = 0 ;

`````` for( int i = 0  ; i < n and k>0 ; i++ , k--  )
ans += count[i] ;
``````

// cout << ct_even <<" " << ct_odd <<"\n" ;
// for( auto i : count )cout << i <<" " ;
// cout <<"\n" ;

`````` cout << ans <<"\n" ;
return ;
``````

}

int main(){
ios::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;

``````int TC ; cin >> TC ;
while( TC-- )
{
S() ;
}
``````

}

on test case 2
what’s wrong in this code ??
2 test cases were worng

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

int steps_till_odd(int x){
int count =0;
while(x%2==0){
count++;
x/=2;
}
return count;
}
int main(){
int t,n;
cin>>t;
while(t–){
cin>>n;
vector v;
int ce=0,co=0,ans=0;
int arr[2n];
for (int i=0;i<2
n;i++){
cin>>arr[i];
if(arr[i]%2) co++;
else {
ce++;
v.push_back(steps_till_odd(arr[i]));
}
sort( v.begin(), v.end() );
}
if (co>ce) ans=abs((co-ce)/2);
else if (co<ce){
int dc=(ce-co)/2;
for(int i=0;i<dc;i++){
ans+=v[i] ;
}
}
cout <<ans<<endl;
}
return 0;
}

why am i getting a tle please someone explain

can anyone tell me why abs(number_of_even_nos-number_of_odd_nos)/2 is not giving right answer?

In the constraints there were no 0, all were starting with 1.
1≤Ai≤109