# Strange Swaps Insomnia 2018

Can anyone share their approach with proof if any ? I am unable to understand the editorial

Lets look at the case where k < n/2. In this case, for every position, you can always swap it with one of the two extreme positions ie., 1 and n. So, for the first (smallest) number, if its already in a position where it can be swapped with the first position, you’ll swap it. Else, you’ll swap it with the nth position and then swap with position 1.

Following this process, suppose that you already moved the smallest ‘i’ numbers to the first ‘i’ positions. Now, you need to move the next smallest number to position ‘i+1’, Now, at least one of the extreme positions will be swappable with i+1 (by swappable, I mean that the distance will be > k), suppose that this extreme position is ‘n’, then you need to first bring your number to position ‘n’. If your number is swappable with ‘n’, then you’ll simply swap twice you’re done.

For the other cases, ie., i+1 is swappable with 1 or, your number is not swappable with ‘n’ or both you will swap your number with position 1 (either directly or through n), then swap it with position i+1 and bring back the number in position 1. The logic for k>=n/2 is also same, the positions that are not far enough from either ends can’t be used, and for every other position, there will always be one extreme position that it can move to.

I have paste same text here https://ideone.com/i4LBmG

I don’t know why ="" are appearing. Just treat them as space

My approach

Assume 0- based indexing

i= index of element

(i-k-1>=0||i+k+1<n)==true then we can place i anywhere in array with index j satisfying (j-k-1>=0||j+k+1<n)==true. And if this condition is false then we cannot move i anywhere.

e.g. if we want to swap i with index j.

Also abs(i-j)>k then we can swap them directly.

Assume i<j

if(j+k+1<n == true ) implies i+k+1<n is also true as i<j

then we can swap i with n-1. i.e ai at index n-1, a[n-1] at i, aj at j

Next swap j with n-1. now ai at j, a[n-1] at i, aj at n-1

Next swap j with n-1. now ai at j, aj at i, a[n-1] at n-1

If above condition is not true but i-k-1>=0 and j-k-1>=0

then we can chose index 0 instead of n-1 and proceed as above to swap i,j

So, Basically for all index i satisfying i-k-1>=0||i+k+1<n can be placed anywhere. And those which does not satisfy this condition cannot move.

So we sort all elements excluding the index which does not satisfy this condition.