Find Maximum number possible by doing at-most K swaps - GeeksforGeeks
Given a positive integer, find maximum integer possible by doing at-most K swap operations on its digits.
Given a positive integer, find maximum integer possible by doing at-most K swap operations on its digits.
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.
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++)
{
// and 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]);
}
}
}
}
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.
Read full article from Find Maximum number possible by doing at-most K swaps - GeeksforGeeks2. Find maximum/minimum integer possible by doing exactly K swap operations on its digits.