problem - https://www.codechef.com/problems/MINPERM

mycode - https://www.codechef.com/viewsolution/33341554

The first sub-task is successfully submitted but my code is not able to pass the second sub-task.Please Help

problem - https://www.codechef.com/problems/MINPERM

mycode - https://www.codechef.com/viewsolution/33341554

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.