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

1. 125914
2. 125941
3. 129145

, would be the no. in the increasing order.

In this, we divide the question into two parts

1. We figure out the Kth no.
2. 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:-

1. We identify if there is and preceding no. smaller. ( remember 54321 cant have any permutation which is bigger than that)
2. As soon as we encounter a no. smaller, we position it such that the number later than that should not be greater than it.
3. 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 😀