Find Maximum number possible by doing at-most K swaps

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
9 upvotes
Asked in companies
OlaIntuitNatwest Group

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.
Detailed explanation ( Input/output format, Notes, Images )

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

Sample input 1 :

1
5 2
0 4 1 2 3

Sample output 1:

4 3 1 2 0

Explanation For Sample Input 1 :

Given 'K' : 2, so the two swaps which will result in the maximum possible number will be :
Swapping indices 1 and 2, resultant array [4,0,1,2,3].
Swapping indices 2 and 5, resultant array [4,3,1,2,0].

Sample input 2 :

1
7 4
9 2 6 4 3 7 1

Sample output 2 :

9 7 6 4 3 2 1

Explanation For Sample Input 2 :

Given 'K' : 4, so at most 4 swaps which will result in the maximum possible number are :
Swapping indices 2 and 6, resultant array [9,7,6,4,3,2,1].
Now the resultant array will result in a maximum possible number, so we do not need to perform more operations.
Hint

Find out all the possible combinations by using recursion.

Approaches (2)
Brute Force

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 :

 

  1. Given array ‘NUM’.
  2. Create an integer array of size ‘N’ (say, ‘maxNum’) initialized to ‘NUM’.
  3. Define a recursive function say ‘SOLVE’ which will receive 3 parameters which are: ‘NUM’, ‘K’ and ‘maxNum’.
  4. Base Case :
    • If ‘K’ is equal to 0 then return, as we are out of operations.
  5. 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.
  6. Finally, return ‘maxNum’.
Time Complexity

O((N^2)^K), where ‘N’ is the length of the array and ‘K’ is the maximum operation we can use.

 

As in each recursive call, we are further making ‘N’^2 recursive calls till 'K' is greater than 0. So total time complexity is  O((N^2)^K).

Space Complexity

O(N), where ‘N’ is the length of the array.

 

‘N’ recursive calls are made until the value of ‘K’ is greater than 0. So total space complexity is O(N).

Code Solution
(100% EXP penalty)
Find Maximum number possible by doing at-most K swaps
Full screen
Console