Click here to Skip to main content
15,921,212 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
Minimum no of swaps to be done in an array such that, no two adjacent elements are same.

n = 6 a[] = {1, 1, 5, 2, 5, 5} answer = 1 ( swap a[0] with a[4] or a[5] )

n = 8 a[] = {1, 5, 5, 1, 4, 6, 1, 1} answer = 2 (swap a[0] with a[1] and a[5] with a[6] )
n = 8 a[] = {3, 1, 1, 5, 3, 3, 5, 5} answer = 2 (swap a[0] with a[1] and a[5] with a[6] )
indexing from zero in above examples.

Refer for question: Minimum no of swaps to be done in an array such that, no two adjacent elements are same. - Codeforces[^]

What I have tried:

Logic 1: count total number of consecutive pairs, and subtract it from the count of remainder elements. But it doesnt seem to work in all cases.
Posted
Updated 6-Feb-18 9:40am

1 solution

This is a contest, so by definition, you have to find a solution yourself.
So if we give you a solution, it will mean that you failed.
Quote:
Logic 1: count total number of consecutive pairs, and subtract it from the count of remainder elements. But it doesnt seem to work in all cases.

That mean that you have to refine your algorithm.
Find samples that don't work and search what changes to do to your algorithm.
Note that some samples can have no solution:
n = 4 a[] = {1, 1, 2, 1} answer = 0, no solution
n = 5 a[] = {1, 1, 2, 1, 2} answer = 2  (swap a[1] with a[2] and a[3] with a[4] )

[Update]
Quote:
Im not able to solve the question, and there is not much help online.

Try to device a brut force algorithm: try every possible swap and combinations of multiples swaps.
 
Share this answer
 
v2
Comments
Member 13664362 6-Feb-18 16:57pm    
Im not able to solve the question, and there is not much help online.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900