Given a positive integer, find maximum integer possible by doing at-most K swap operations on its digits.
Input: M = 254, K = 1 Output: 524 Input: M = 254, K = 2 Output: 542 Input: M = 68543, K = 1 Output: 86543 Input: M = 7599, K = 2 Output: 9975 Input: M = 76543, K = 1 Output: 76543 Input: M = 129814999, K = 4 Output: 999984211
Idea is to consider every digit and swap it with digits following it one at a time and see if it leads to the maximum number. We repeat the process K times. The code can be further optimized if we swap only if current digit is less than the following digit.
Below is implementation of above idea –
# Python3 program to find maximum
# integer possible by doing at-most
# K swap operations on its digits.
# utility function to swap two
# characters of a string
def swap(string, i, j):
return (string[:i] + string[j] +
string[i + 1:j] +
string[i] + string[j + 1:])
# function to find maximum integer
# possible by doing at-most K swap
# operations on its digits
def findMaximumNum(string, k, maxm):
# return if no swaps left
if k == 0:
n = len(string)
# consider every digit
for i in range(n – 1):
# and compare it with all digits after it
for j in range(i + 1, n):
# if digit at position i is less than
# digit at position j, swap it and
# check for maximum number so far and
# recurse for remaining swaps
if string[i] < string[j]: # swap string[i] with string[j] string = swap(string, i, j) # If current num is more than # maximum so far if string > maxm:
maxm = string
# recurse of the other k – 1 swaps
findMaximumNum(string, k – 1, maxm)
string = swap(string, i, j)
# Driver Code
if __name__ == “__main__”:
string = “129814999”
k = 4
maxm = [string]
findMaximumNum(string, k, maxm)
# This code is contributed
# by vibhu4agarwal
The above code can further be optimized by stopping our search if all digits are already sorted in decreasing order. Please do share with us if you find more efficient ways to solve this problem.
1. Find minimum integer possible by doing at-least K swap operations on its digits.
2. Find maximum/minimum integer possible by doing exactly K swap operations on its digits.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
This article is attributed to GeeksforGeeks.org