Given a positive integer, find the maximum integer possible by doing at-most K swap operations on its digits.Examples:
Input: M = 254, K = 1
Output: 524
Swap 5 with 2 so number becomes 524
Input: M = 254, K = 2
Output: 542
Swap 5 with 2 so number becomes 524
Swap 4 with 2 so number becomes 542
Input: M = 68543, K = 1
Output: 86543
Swap 8 with 6 so number becomes 86543
Input: M = 7599, K = 2
Output: 9975
Swap 9 with 5 so number becomes 7995
Swap 9 with 7 so number becomes 9975
Input: M = 76543, K = 1
Output: 76543
Explanation: No swap is required.
Input: M = 129814999, K = 4
Output: 999984211
Swap 9 with 1 so number becomes 929814991
Swap 9 with 2 so number becomes 999814291
Swap 9 with 8 so number becomes 999914281
Swap 1 with 8 so number becomes 999984211
Find Maximum number possible by doing at-most K swaps - GeeksforGeeks
// C++ program to find maximum
// integer possible by doing
// at-most K swap operations
// on its digits.
#include <bits/stdc++.h>
using namespace std;
// Function to find maximum
// integer possible by
// doing at-most K swap
// operations on its digits
void findMaximumNum(
string str, int k, string& max)
{
// Return if no swaps left
if (k == 0)
return;
int n = str.length();
// Consider every digit
for (int i = 0; i < n - 1; i++) {
// Compare it with all digits after it
for (int j = i + 1; j < n; j++) {
// 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 (str[i] < str[j]) {
// swap str[i] with str[j]
swap(str[i], str[j]);
// If current num is more
// than maximum so far
if (str.compare(max) > 0)
max = str;
// recurse of the other k - 1 swaps
findMaximumNum(str, k - 1, max);
// Backtrack
swap(str[i], str[j]);
}
}
}
}
// Driver code
int main()
{
string str = "129814999";
int k = 4;
string max = str;
findMaximumNum(str, k, max);
cout << max << endl;
return 0;
}