There are n-pairs and therefore 2n people. everyone has one unique number ranging from 1 to 2n. All these 2n persons are arranged in random fashion in an Array of size 2n. We are also given who is partner of whom. Find the minimum number of swaps required to arrange these pairs such that all pairs become adjacent to each other.
n<10^3 arr.size<10^3
Input: n = 3
pairs[] = {1->3, 2->6, 4->5} // 1 is partner of 3 and so on
arr[] = {3, 5, 6, 4, 1, 2}
Output: 2
We can get {3, 1, 5, 4, 6, 2} by swapping 5 & 6, and 6 & 1
(Google Interview)
http://www.lmgtfy.com/?q=Minimum+swap+for+arranging+adacent+pair
your jokes are worth your rating
That wasn't a joke... I was just telling him to first google the question and then only ask here.
PS-> Your views tell a lot about your thinking about people below you(rating wise)... God bless you :-)
Let's call a spade a spade. That wasn't a friendly advice to google the question. He is wise who says nothing when he has nothing to say.
PS-> Your jokes tell a lot about your thinking about people below you(rating wise)... God bless you :-)
Up. I met this problem before and know linear reference solution but I can't prove it :(
The solution which makes swaps along the cycles of permutation?
Yep.
Consider first two elements. If they are partners then skip them and move to the next two elements. Otherwise find a pair for any of these two elements (suppose the pair was among a[2k] and a[2k + 1]), make swap, now move to elements with indexes 2k and 2k + 1 and repeat step.