15,921,212 members
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

Solution 1

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.

v2