Find Maximum Number Possible by Doing At Most K Swaps in C++

In this problem, we are given two integer values n and k. Our task is to find the Maximum number possible by doing at-most K swaps. 

Problem description: Here, we need to calculate the number which is maximum and created after swapping at-most k digits of the number.

Let’s take an example to understand the problem, 

Input: n = 538 k = 1

Output: 835

Explanation: 

We will swap 8 and 5.

Solution Approach

To solve the problem, we need to swap digits of the number k times and check if the number from is maximum.  

We need to find the maximum digit of the number and then swap the element at first index. And so on for the first k index of the numbers.

Program to illustrate the working of our solution

Example

Live Demo

#include <bits/stdc++.h>
using namespace std;

void calcMaxNumAfterSwap(string number, int k, string& maxString, int n){
   
   if (k == 0)
      return;
   for (int i = 0; i < n - 1; i++) {
      for (int j = i + 1; j < n; j++) {
         if (number[i] < number[j]) {
            swap(number[i], number[j]);
            if (number.compare(maxString) > 0)
               maxString = number;
            calcMaxNumAfterSwap(number, k - 1, maxString, n);
            swap(number[i], number[j]);
         }
      }
   }
}

int main(){
   
   string str = "15263";
   int k = 3;
   int size = str.length();
   string maxString = str;
   calcMaxNumAfterSwap(str, k, maxString, size);
   cout<<"The maximum number created after "<<k<<" swaps is "<<maxString;

   return 0;
}

Output

The maximum number created after 3 swaps is 65321