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

Java

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 🙂
 


Get great deals at Amazon




Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Ankita
Guest
Ankita

Thanks for sharing this article. Can you please tell what will be the time complexity of this? Is it O( k^N^2) ?

Guest
Guest
Guest

I think greedy solution will be best choice to solve this problem