problem - MINPERM Problem - CodeChef
mycode - CodeChef: Practical coding for everyone
The first sub-task is successfully submitted but my code is not able to pass the second sub-task.Please Help
Sir,although i did not go through your code but I felt that you have used a very cumbersome logic.
There is a simple logic you can follow.
if n is even
exchange each number with it’s next number
Eg. if n=4 then the smallest permutation is [1,2,3,4].You just need to exchange 2 with 1 and 3 with 4 and the result [2,1,4,3] will be the lexicographically smallest good permutation
if n is odd
then leave out the last 3 nos. and perform the same steps as above with the remaining.As for the last three just perform a circular rotation of the numbers at those indices
Eg n=5 then the smallest permutation is [1,2,3,4,5]. Leave out last 3 and swap 2 with 1.So it becomes [2,1,3,4,5]. After that perform circular rotation on 3,4,5 ->4,5,3. Then the final ans becomes[2,1,4,5,3].
Complexity: O(n)
Hope it helps.Feel free to ask any further doubts or if anything is unclear.
1 Like
You explained quite clearly so i didn’t had any doubt and it helped a lot.
Thank you so much for helping me out.