Python Program to find Maximum number possible by doing at-most K swaps
In this tutorial, we will see how to find the maximum number possible by doing at most K swaps in the number in Python.
Consider the following examples:
INPUT: Number=189 K=1 OUTPUT: 981 EXPLANATION: 1 is swapped with 9 INPUT: Number=198 K=2 OUTPUT: 981 EXPLANATION: Swap 9 with 1 so the number becomes 918. 981 is the output after swapping 8 with 1. INPUT: Number=98765 K=1 OUTPUT: 98765 EXPLANATION: No swap requirement. INPUT: Number=139714999, K = 4 OUTPUT: 999974211 EXPLANATION: Swap 9 with 1 so number becomes 939714991 Swap 9 with 3 so number becomes 999714391 Swap 9 with 7 so number becomes 999914371 Swap 1 with 7 so number becomes 999974311
Find Maximum number possible by doing at-most K swaps in Python
In this program, we consider every digit and swap it with the following digits and check if it produces the maximum number. The function is called recursively K times.
#Strings are immutable. #Therefore returning a new string with swapped values def swap(string, i, j): return (string[:i] + string[j] + string[i + 1:j] + string[i] + string[j + 1:]) #Recursive function def Afterkswap(string, k, maxm): # return if no swaps left if k == 0: return n = len(string) for i in range(n - 1): for j in range(i + 1, n): if string[i] < string[j]: string = swap(string, i, j) #if the returned string is greater than the current number if string > maxm: maxm = string #Recursively call findMaximumNum Afterkswap(string, k - 1, maxm) # backtrack string = swap(string, i, j) # Driver Code s= "645957321" k = 5 maxm = [s] Afterkswap(string, k, maxm) print("Greatest Number after K swaps:",maxm)
Greatest Number after k swaps: 976554321
Hope you liked this tutorial!