Last Updated: 13 Feb, 2021

Find Maximum number possible by doing at-most K swaps

Moderate

Asked in companies

Solve now

Problem statement

You are given an array of 'N' non-negative integers, representing the digits of a number, and an integer 'K'. Your task is to find the maximum possible number that can be made by swapping the digits of the given number at most 'K' times.

Note :

1. The input may have 0 before the most significant digit, [0,3,5,7] is a valid input and it represents number 357.
2. Digits in the number can be repeated, i.e [3, 3, 4, 4] is a valid input and it represents the number 3344.

Input Format :

The first line of input contains a single integer 'T', representing the number of test cases.
Then the test cases follow.

The first line of each test case contains two space-separated integers 'N' and 'K', denoting the size of the array and the number of swaps permitted respectively.

The second line contains 'N' space-separated integers representing the digits as described in the problem statement.

Output format :

For each test case, print the space-separated digits of the maximum number possible.

Note :

You don’t have to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1<= T <=10
2 <= N <= 10
0 <= K <= min(N,5)
0 <= NUM[i] <= 9

Time Limit: 1 sec

Solve now

Approaches

01 Approach

The idea is to generate all the possible numbers by trying all the possible combinations of indices at most ‘K’ times. We will do this task with a recursive function and each time we swap two indices we will decrease the value of ‘K’ by 1. So base case is when ‘K’ is equal to zero and each time when we swap indices we will check whether the current number is the maximum possible or not.

Here is the algorithm :

Given array ‘NUM’.
Create an integer array of size ‘N’ (say, ‘maxNum’) initialized to ‘NUM’.
Define a recursive function say ‘SOLVE’ which will receive 3 parameters which are: ‘NUM’, ‘K’ and ‘maxNum’.
Base Case :
- If ‘K’ is equal to 0 then return, as we are out of operations.
Recursive Calls :
- Run a loop over ‘NUM’ from 0 to ‘N’ (say, iterator ‘i’) and do :
  - Run a loop over ‘NUM' from ‘i’ to ‘N’ (say, iterator ‘j’) and do :
    - Swap ‘NUM’[i] and ‘NUM’[j]
    - If ‘NUM’ is greater than ‘maxNum’ then update ‘maxNum’ to ‘NUM’.
    - Update ‘K’ to ‘K’ - 1 as we have used an operation.
    - Make a call to ‘SOLVE’ with updated values of ‘maxNum’, ‘NUM’ and ‘K’.
    - Get the original array back by swapping ‘NUM’[i] and ‘NUM’[j].
    - Also update ‘K’ to ‘K’ + 1, as we have reversed an operation.
Finally, return ‘maxNum’.

Solve now

02 Approach

We can improve the time complexity of the previous - discussed approach by making a slight modification. So to get the maximum number a digit must be swapped only with the maximum digit available on its right-hand side and which is also greater than the current digit.

We will do this task with a recursive function and each time we swap two indices we will decrease the value of ‘K’ by 1. So, the base case will be when ‘K’ is equal to zero and each time when we swap indices we will check whether the current number is the maximum possible or not.

Here is the algorithm :

Given input array (say, ‘NUM’).
Create an integer variable (say, ‘CURR’) and initialise it to 0.
Create an integer array of size 'N' (say, ‘maxNum’) initialized to ‘NUM’.
Define a recursive function (say, ‘SOLVE’) which will receive 4 parameters which are : ‘CURR’, ‘NUM’, ‘K’ and ‘maxNum’.
Base Case :
- If ‘K’ is equal to 0 then return, as we are out of operations.
Recursive Calls :
- Create an integer variable (say, ‘MAX_VAL’) and initialise it to NUM[CURR].
- Run a loop over ‘NUM’ from ‘CURR’ + 1 to ‘N’ (say, iterator ‘i’) and do :
  - Find the maximum digit greater than ‘MAX_VAL’ and set 'MAX_VAL' equal to that digit.
- If ‘MAX_VAL’ is equal to ‘NUM’[CURR] then we know we can not swap current digit with any other digit so do:
  - Update ‘CURR’ to ‘CURR’ + 1.
  - Make a call to the ‘SOLVE’ function.
- Else do :
  - Run a loop over ‘NUM’ from ‘CURR’ + 1 to ‘N’ (say, iterator ‘i’) and do :
    - If ‘NUM’[i] is equal to ‘MAX_VAL’ then do :
      - Swap ‘NUM’[i] and ‘NUM’[j]
      - If ‘NUM’ is greater than ‘maxNum’ then update ‘maxNum’ to ‘NUM’.
      - Update ‘K’ to ‘K’ - 1 as we have used an operation.
      - Update ‘CURR’ to ‘CURR’ +1
      - Make a call to ‘SOLVE’ with updated values of ‘CURR’, ‘maxNum’, ‘NUM’ and ‘K’.
      - Get the original array back by Swapping ‘NUM’[i] and ‘NUM’[j].
      - Also update ‘K’ to ‘K’ + 1, as we have reversed an operation.
      - Update ‘CURR’ to ‘CURR’ - 1.
Finally, return ‘maxNum’.

Solve now