PROBLEM LINK:
Author: Dheeraj Bhagchandani
Tester: Bhupat Jangid
Editorialist: Dheeraj Bhagchandani
DIFFICULTY:
SIMPLE-EASY
PREREQUISITES:
Basic Implementation, Greedy, Two Pointer’s
PROBLEM:
Chef has N items in his Shop (numbered 1 through N); And for Each valid i (1<=i<=N). the weight of the i−th item is Wi. Since Chef is very sensitive in nature.
Chef wants to arrange all even weights items one side and odd weights items on another side. Chef can arrange two adjacent items with help of swapping at one operation. Chef wants a minimum number of operations required to arrange All Even weights item on one side and All Odd weights item to the another side.
QUICK EXPLANATION:
So, Firstly we Arrange All Even Numbers on the Right Side and Calculate the Total number of swaps let it denotes by ans1. Secondly, we Arrange All Even Numbers on the Left Side and Calculate the Total number of swaps let it denotes by ans2. At last, the answer is a minimum of both.
Answer : min(ans1,ans2)
EXPLANATION:
It is easy to understand that, in the End, All even or odd numbers are different sides not overlaps each other. So we simply do that first we arrange all even/odd numbers on the left side. or all even/odd numbers on the right side. And after that’s we calculate the answer as a minimum of both steps.
Example: we have an Array = [1,6,7,5,2]
first, we arrange all odd numbers left side. Total Operations: 4; or vise versa
Second, we arrange all odd numbers right side. Total Operations: 2; or vise versa
Answer : Min(4,2) => 2 Operations.
SOLUTIONS:
Setter's Solution
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-- != 0) {
int n = sc.nextInt();
int arr[] = new int[n];
ArrayList<Integer> even_index = new ArrayList<Integer>();
for(int i=0; i<n; i++) {
arr[i] = sc.nextInt();
if(arr[i] %2 == 0)even_index.add(i);
}
// first arrange all even number left side
int left = 0;
for(int i=0; i<even_index.size(); i++) {
int diff = even_index.get(i) - i;
left+=diff;
}
// arrange all even number right side
int right = 0;
int set_index = n-1;
for(int i=even_index.size()-1; i>=0; i--) {
int diff = set_index - even_index.get(i);
right+=diff;
set_index--;
}
// ans min of left and right
int ans = Math.min(left, right);
System.out.println(ans);
}
}
}
1st Tester's Solution
for y in range(int(input())):
n=int(input())
lst=list(map(int,input().split()))
cnt1=cnt2=0
p1=p2=n-1
for i in range(n-1,-1,-1):
if lst[i]%2==0:
cnt2+=p2-i
p2-=1
else:
cnt1+=p1-i
p1-=1
print(min(cnt1,cnt2))
2nd Tester's Solution
#include <bits/stdc++.h>
typedef long long ll;
#define vi vector<ll>
#define pi pair<ll,ll>
#define st set<ll>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define fo(i,a,b) for(ll i = a; i <= b; i++)
#define Rfo(i,a,b) for(ll i = a; i >= b; i--)
#define FOREACH(it, l) for (auto it : l)
#define sortVi(v) sort(v.begin(),v.end())
#define sortViR(v) sort(v.begin(),v.end(), greater<ll>())
#define sortArr(arr) sort(arr,arr+n)
#define sortArrR(arr) sort(arr,arr+n greater<ll>())
#define Sq(a) (a)*(a)
#define mod 1000000007
using namespace std;
bool prime(ll n){
if(n<2) return false;
fo (i,2,sqrt(n)) {
if (n % i == 0)
return false;
}
return true;
}
ll modPower(ll x,ll b,ll m)
{
if (b == 0) return 1;
if (b == 1) return x;
ll r = modPower(x, b / 2,m);
r=(r*r)%m;
if (b%2 != 0) r = (r * x)%m;
return r;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll t;
cin >> t;
while(t--)
{
ll a, b, c, d, x, y, z, i, j, k, n, m,h;
ll sum=0;
ll cnt_1 = 0;
ll cnt_2 = 0;
cin>>n;
ll arr[n];
fo(i, 0, n - 1) cin >> arr[i];
j = n - 1;
while(arr[j]%2==0){
j--;
}
Rfo(i,j-1,0){
if(arr[i]%2==0)
{cnt_1 += (j - i);
j--;}
}
j = 0;
while(arr[j]%2==0){
j++;
}
fo(i,j,n-1){
if(arr[i]%2==0)
{cnt_2 += (i-j);
j++;
}
}
cout << min(cnt_1,cnt_2) << "\n";
}
return 0;
}
