PROBLEM LINK:
PRACTICE
Editorialist: Avishake Maji
DIFFICULTY:
MEDIUM
PREREQUISITES:
Map, Array
PROBLEM:
It’s Christmas time, Santa’s friends are helping him to arrange the gifts. Franklin is a new member of Santa’s group and he too help the others in arranging the gifts. Let n be the number of gifts. Santa has a unique technique of ordering ,he put a number on each gift and then he write the order of the gifts on a piece of paper and give it to his friends .But Franklin being a new member does not know about this technique so he arrange the gifts haphazardly without maintaining the order. But then one of the other member told him about this technique. Franklin finds himself in deep trouble and asks for your help. You are given the order of the gifts that Santa has given on the paper and also the order by which Franklin arranges the gifts. You have to find the minimum number of swaps required to convert Franklin’s order to Santa’s.
EXPLANATION:
We are told to rearrange the array in such a way that Franklin’s array to similar to Santa’s. To solve this problem we are using map . Considering the element elements of Franklin as key and index as value we storing them in a map.
If arr[i]!=brr[i] then we are swapping the elements and also updating the map.
SOLUTION:
#include <iostream>
#include<map>
#define ll long long int
using namespace std;
void solve();
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
void solve()
{
ll n;
cin>>n;
ll arr[n+1];
ll brr[n+1];
map<ll,ll>mp;
for(ll i=0;i<n;i++)
cin>>arr[i];
for(ll i=0;i<n;i++)
{
cin>>brr[i];
mp[brr[i]]=i;
}
ll mi=0;
for(ll i=0;i<n;i++){
if(arr[i]!=brr[i]){
ll t=brr[i];
brr[i]=brr[mp[arr[i]]];
brr[mp[arr[i]]]=t;
mp[brr[mp[arr[i]]]]=mp[arr[i]];
mp[brr[i]]=i;
mi++;
}
}
cout<<mi<<endl;
}