# Minimum Adjacent Swaps to Reach the Kth Smallest Number

This is an interesting question.

The same logic can be applied to the next permutation problem.

C++ has an inbuilt function for the next permutation which might be useful in OA but clearly not in F2F.

Basically in this question, we have to find a no. just bigger than the no. given K times.

If the no. is 125491 then

- 125914
- 125941
- 129145

, would be the no. in the increasing order.

In this, we divide the question into two parts

- We figure out the Kth no.
- We find swaps required to reach that no.

`int getMinSwaps(string num, int k) {`

string perm = num;

while (k -— ) {

for (int i = perm.size()-1; i > 0; — i) {

if (perm[i-1] < perm[i]) {

int ii = i,j = perm.size()-1;

for (; ii <= j && perm[i-1] < perm[ii]; ++ii);

swap(perm[i-1], perm[ii-1]);

while (i < j) swap(perm[i++], perm[j — ]);

break;

}

}

}

int ans = 0;

for (int i = 0; i < num.size(); ++i) {

int ii = i+1;

while (num[i] != perm[i]) {

++ans;

swap(perm[i], perm[ii++]);

}

}

return ans;

}

In the first part of code:-

- We identify if there is and preceding no. smaller. ( remember 54321 cant have any permutation which is bigger than that)
- As soon as we encounter a no. smaller, we position it such that the number later than that should not be greater than it.
- After the swap, we reverse the numbers till the end.

Example:- 1 2 5 4 9 1

swapping 9 and 4 , since we found 4 is smaller than 9

1 2 5 9 4 1

reversing till end

1 2 5 9 1 4 -> 1st greater no.

again:-

1 2 5 9 4 1 -> 2nd greater no.

then swapping 9 with 5

1 2 9 5 4 1

now reversing

1 2 9 1 4 5 -> 3rd greater no.

2nd part of the code is easy as it is just a two-pointer:

1 2 5 9 4 1 -> 1 2 9 1 4 5^ ^

i j

we go on till we find same digits

when it is different we swap and find no. of swaps needed.

Thanks for reading 😀