### wish_me's blog

By wish_me, history, 5 years ago,

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)

• +4

| Write comment?
 » 5 years ago, # |   +10
•  » » 5 years ago, # ^ |   +10 your jokes are worth your rating
•  » » » 5 years ago, # ^ |   0 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 :-)
•  » » » » 5 years ago, # ^ |   0 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 :-)
 » 5 years ago, # | ← Rev. 2 →   +7 Up. I met this problem before and know linear reference solution but I can't prove it :(
•  » » 5 years ago, # ^ |   0 The solution which makes swaps along the cycles of permutation?
•  » » » 5 years ago, # ^ |   +5 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.