Three people are playing a game in which one person is selected first, the second person gives the selected person a number N, and the third person also gives the selected person a number M. The selected person has to maximize the number given by the second person in a way that: 1. (S)he can maximize the number given by the second person only by swapping the adjacent two digits of the number. 2. The number that the third person gives is the maximum number of swaps allowed Find the maximum number that the selected person can achieve.
Answers
Answer:
char[] ch = s.toCharArray();
int i=0;
int max = -1;
int indexOfMax;
while(i<s.length() && swapsAllowed>0)
{
int j = i;
indexOfMax = i;
for(;j <= i+swapsAllowed && j<s.length();j++)
{
if(ch[j]-'0'>max)
{
max = ch[j]-'0';
indexOfMax = j;
}
}
if(indexOfMax == s.length()-1 && j==s.length())
{
return String.valueOf(ch);
}
for(int o=indexOfMax-1; o>=i; o--) // Move the maximum number to front
{ char temp = ch[o+1];
ch[o+1] =ch[o];
ch[o] = temp;
}
max = -1;
swapsAllowed = swapsAllowed - indexOfMax - i;
i++;
}
return String.valueOf(ch);
Explanation:
s = Given input number.
swapsAllowed = maximum no of swaps allowed
Approach - Find the maximum number within the bound of max no of swaps and move that number to first available index.
Answer:
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.
Explanation:
In this problem, one positive integer string is given, we have to find the permutation whose value is maximum by swapping digits’ k times, into different places.
We will solve this problem by choosing a digit and swap it with digits following it one at a time to find a maximum number. We repeat the process k times. The backtracking strategy is working here because when we find a number which is not greater than the previous value, we backtrack to old value and check again.
Input and Output
Input:
A number of multiple digits.
The input is: 129814999
Output:
The maximum value from these digits by swapping them.
The output is: 999984211
Algorithm
maxNum(number, swaps, maxNumber)
Input − The number as a string, the number of swaps and the maxNumber string.
Output − Update the maxNumber to get the largest value.
Begin
if swaps = 0, then
return
n := number of digits in the number
for i := 0 to n-2, do
for j := i+1 to n-1, do
if number[i] < number[j], then
exchange number[i] and number[j]
if number is greater than maxNumber, then
maxNumber := number
maxNum(number, swaps-1, maxNumber)
exchange number[i] and number[j] again for backtrack
done
done
End
Example
#include <iostream>
using namespace std;
void maxNum(string str, int swaps, string &max) {
if(swaps == 0) //when no swaps are left
return;
int n = str.length();
for (int i = 0; i < n - 1; i++) { //for every digits og given number
for (int j = i + 1; j < n; j++) {
if (str[i] < str[j]) { //when ith number smaller than jth number
swap(str[i], str[j]);
if (str.compare(max) > 0) //when current number is greater, make it maximum
max = str;
maxNum(str, swaps - 1, max); //go for next swaps
swap(str[i], str[j]); //when it fails, reverse the swapping
}
}
}
}
int main() {
string str = "129814999";
int swapNumber = 4;
string max = str;
maxNum(str, swapNumber, max);
cout <<"The given number is: " <<str << endl;
cout <<"The maximum number is: "<< max << endl;
}
Output
The given number is: 129814999
The maximum number is: 999984211