Find minimum number possible by doing at-most K swaps

Given a positive integer, find minimum number possible by doing at-most K swap operations upon its digits.


 

For example,


Input: S = 934651, K = 1
Output: 134659

Input: S = 934651, K = 2
Output: 134569

Input: S = 52341, K = 2
Output: 12345 (Only 1 swap needed)

Input: S = 12345, K = 2
Output: 12345 (no change as all digits are already sorted in increasing order)

 

We can use Backtracking to solve this problem. The idea is to consider every digit and swap it with digits following it one at a time and see if it leads to the minimum number. The process is repeated K times.

C++

Download   Run Code

Output:

The minimum number formed by doing at-least 2 swaps is 134569

 
Author: Aditya Goel

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz