EQVAL - Editorial

editorial
, , ,
1

PROBLEM LINK: Balanced Plates

Author: Rishabh Rathi
Tester: Rishabh Rathi

DIFFICULTY:

EASY

PREREQUISITES:

None

PROBLEM:

You are given an array of N integers and want to make all array elements equal.

There are 2 operations possible. Pick any element of array and decrease/increase it

  1. by 1 - Cost of each operation is Rs. X (cost given)
  2. by 2 - Cost of each operation is Rs. 0 (Free)

What is the minimum amount of money you need?

EXPLANATION:

First operation is to change A_i to A_i + 1 or A_i - 1 for Rs. X and in second operation, we can change A_i to A_i + 2 or A_i - 2 for Rs. 0.

So from here, we can deduce that we can change any element to any value if they have same parity (odd to odd/even to even) for free. And to change parity (odd to even/even to odd), we need to spend Rs. X.

So, output minimum of count of odd and even elements in the array multiplied by X.

SOLUTIONS:

Setter's Solution (Python) 
t = int(input())
for _ in range(t):
	n, x = map(int, input().split())
	a = list(map(int, input().split()))
	even = odd = 0
 
	for i in range(n):
		if a[i]%2 == 0:
			even += 1
		else:
			odd += 1
 
	print(min(even, odd)*x)
Tester's Solution (CPP) 
#include <bits/stdc++.h>
using namespace std;
 
void solve(){
	int n, x; cin>>n>>x;
	vector<int> a(n);
	int odd = 0, even = 0;
	
	for(auto &i:a)
		cin>>i;
	
	for(auto i:a){
		if(i%2)
			odd++;
		else 
			even++;
	}

	cout << min(odd, even)*x << '\n';
}

int main(){
	int tt; cin >> tt;
	
	while(tt--){
		solve();
	}
}

Feel free to share your approach. In case of any doubt or anything is unclear, please ask it in the comments section. Any suggestions are welcome :smile:

1 Like