Naive solution for the Largest number in K swaps
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 maximum number. The process is repeated K times. The code can be further optimized, if the current digit is swapped with a digit less than the following digit.
Follow the below steps to Implement the idea:
- Create a global variable that will store the maximum string or number.
- Define a recursive function that takes the string as a number and value of k
- Run a nested loop, the outer loop from 0 to the length of string -1, and the inner loop from i+1 to the end of the string.
- Swap the ith and jth characters and check if the string is now maximum and update the maximum string.
- Call the function recursively with parameters: string and k-1.
- Now again swap back the ith and jth character.
Below is the Implementation of the above approach:
// 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;
}
// Java program to find maximum
// integer possible by doing
// at-most K swap operations
// on its digits.
import java.util.*;
class GFG{
static String max;
// Function to find maximum
// integer possible by
// doing at-most K swap
// operations on its digits
static void findMaximumNum(char[] str,
int k)
{
// 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]
char t = str[i];
str[i] = str[j];
str[j] = t;
// If current num is more
// than maximum so far
if (String.valueOf(str).compareTo(max) > 0)
max = String.valueOf(str);
// recurse of the other
// k - 1 swaps
findMaximumNum(str, k - 1);
// Backtrack
char c = str[i];
str[i] = str[j];
str[j] = c;
}
}
}
}
// Driver code
public static void main(String[] args)
{
String str = "129814999";
int k = 4;
max = str;
findMaximumNum(str.toCharArray(), k);
System.out.print(max + "\n");
}
}
// This code is contributed by 29AjayKumar
# 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:
return
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[0]:
maxm[0] = string
# recurse of the other k - 1 swaps
findMaximumNum(string, k - 1, maxm)
# backtrack
string = swap(string, i, j)
# Driver Code
if __name__ == "__main__":
string = "129814999"
k = 4
maxm = [string]
findMaximumNum(string, k, maxm)
print(maxm[0])
# This code is contributed
# by vibhu4agarwal
// C# program to find maximum
// integer possible by doing
// at-most K swap operations
// on its digits.
using System;
class GFG{
static String max;
// Function to find maximum
// integer possible by
// doing at-most K swap
// operations on its digits
static void findMaximumNum(char[] str,
int k)
{
// 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]
char t = str[i];
str[i] = str[j];
str[j] = t;
// If current num is more
// than maximum so far
if (String.Join("", str).CompareTo(max) > 0)
max = String.Join("", str);
// recurse of the other
// k - 1 swaps
findMaximumNum(str, k - 1);
// Backtrack
char c = str[i];
str[i] = str[j];
str[j] = c;
}
}
}
}
// Driver code
public static void Main(String[] args)
{
String str = "129814999";
int k = 4;
max = str;
findMaximumNum(str.ToCharArray(), k);
Console.Write(max + "\n");
}
}
// This code is contributed by gauravrajput1
<script>
// Javascript program to find maximum
// integer possible by doing
// at-most K swap operations
// on its digits.
let max;
// Function to find maximum
// integer possible by
// doing at-most K swap
// operations on its digits
function findMaximumNum(str,k)
{
// Return if no swaps left
if (k == 0)
return;
let n = str.length;
// Consider every digit
for (let i = 0; i < n - 1; i++)
{
// Compare it with all digits
// after it
for (let 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]
let t = str[i];
str[i] = str[j];
str[j] = t;
// If current num is more
// than maximum so far
if ((str).join("")>(max) )
max = (str).join("");
// recurse of the other
// k - 1 swaps
findMaximumNum(str, k - 1);
// Backtrack
let c = str[i];
str[i] = str[j];
str[j] = c;
}
}
}
}
// Driver code
let str = "129814999";
let k = 4;
max = str;
findMaximumNum(str.split(""), k);
document.write(max + "<br>");
// This code is contributed by unknown2108
</script>
Output
999984211
Time Complexity: O((N2)k). For every digit, N2 recursive calls are generated until the value of k is 0 Thus O((N2)k).
Auxiliary Space: O(N). This is the space required to store the output string.
Find Maximum number possible by doing at-most K swaps
Given two positive integers M and K, find the maximum integer possible by doing at-most K swap operations on its digits.
Examples:
Input: M = 254, K = 1
Output: 524
Explanation: Swap 5 with 2 so number becomes 524Input: M = 254, K = 2
Output: 542
Explanation: Swap 5 with 2 so number becomes 524, Swap 4 with 2 so number becomes 542Input: M = 68543, K = 1
Output: 86543
Explanation: Swap 8 with 6 so number becomes 86543Input: M = 7599, K = 2
Output: 9975
Explanation: Swap 9 with 5 so number becomes 7995, Swap 9 with 7 so number becomes 9975Input: M = 76543, K = 1
Output: 76543
Explanation: No swap is required.Input: M = 129814999, K = 4
Output: 999984211
Explanation: 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