What is meant by largest permutation possible?

#1

What is meant by largest permutation possible??what is largest permutation in case when N=10,K=100 and numbers are 9,8,7,6,5,4,3,2,1,10

#2

Hello @wadhwasaab,

The largest permutation would be same in this case:
9 8 7 6 5 4 3 2 1 10

Combine all the elements together as a string:
98765432110

This the largest number you can have with the combination of above numbers.
Thus, Largest permutation is 9 8 7 6 5 4 3 2 1 10 and it will require 0 swaps.

Now, let’s take a better example:

Input: N=5, K=3
arr[] = {4, 5, 2, 1, 3}
Output: 5 4 3 2 1

Explanation:
Swap 1st and 2nd elements: 5 4 2 1 3
Swap 3rd and 5th elements: 5 4 3 1 2
Swap 4th and 5th elements: 5 4 3 2 1

Thus largest number that you can form using above digit is 54321.

Hope, your doubt is cleared.
Give a like if you are satisfied.

#3

In the hint video for this question it is given that best position(index) for a number is N-(that number), if we take that into consideration then the ans is 10,9,8,7,6,5,4,3,2,1 for the N=10 and K=9
but the largest permutation should be 98765432110

#4

Yes, you are right.
I just confirmed this thing for the mentor,
The largest number in the sequence will come at first position.
In simple terms you have to sort the sequence in decreasing order with a limit of k swaps.

I apologize for my previous reply.
Hope, know your doubt is resolved.

1 Like