how do i go with it
all i know is i gotta sort an array but what after it
I need to know the process
You have to sort the array only when k >= n. And then display the array in reverse order for largest permutation.
When k < n, you have to do k swaps to find the largest possible permutation starting from the index 0.
Try writing some code and tell me if you are able to get the correct answer. Else I will help you.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.
@sshreya2912,
There’s no need of replacing, you are over-complicating a simple problem. Just greedily choose, k largest elements to appear initially in descending order, also no swap is needed, if that number is already on it’s right place.
how to greedily choose, k largest elements can i get the algorithm to it or the code
@sshreya2912,
Think of it yourself, I am sure you can do it, no one would benefit if I just provide the code for everything. Brainstorm, and it’s lockdown, so anyway we have a lot of time to brainstorm, right?
Hint: You know the largest k numbers will be n,n-1,n-2,…,n-k+1…and they have to occur in that order, starting from left. So, a[1]=n, a[2]=n-1, a[3]=n-2…a[k]=n-k+1, So if the given array does not have the required element at its correct position, you will need to spend a swap to bring it there, and if the element is already at right place, no need to do anything for it.
in order to compare if the elemt is in the right place i gotta copy the given array and sort the copied array to compare with the previous one…would that be okay?
should i create a map against the sorted array , if not how do i access the greatest number in the first array so as to swap it
i gotta use a nested loop?
@sshreya2912,
Nested loop will be O(n^2), but we need to do it in less than that. So, yeah any preprocessing would certainly help.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.
https://ide.codingblocks.com/s/283425 this is my code, I am getting tle for last tc while AC for rest please rectify and tell me my mistake
@sshreya2912 your code is failing for cases where k swaps are not possible, ie less than k swaps need to be done to get the maximum possible permutation. But your condition is while(k) so that loop will never break if k does not reach 0 and hence it goes in an infinite loop.
For example
array = 1 5 4 3 2 6
this will run fine if k = 1, but it will go into an infinite loop if k > 1
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.