Re: 11925 - Generating Permutations

All about problems in Volume 119. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Repon kumar Roy
Learning poster
Posts: 96
Joined: Tue Apr 23, 2013 12:54 pm

Re: 11925 - Generating Permutations

Post by Repon kumar Roy » Wed Oct 01, 2014 9:35 am

STL list is the appropriate data structure for this problem . Thanks brain fry

Code: Select all

Cut after AC  :) 
Last edited by Repon kumar Roy on Wed Oct 08, 2014 6:55 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11925 - Generating Permutations

Post by brianfry713 » Wed Oct 01, 2014 11:55 pm

I solved it using a list initialized to 1 through n and an array to keep track of the position of each integer in the final permutation.

while the list does not match the final permutation:
First see if a type 1 operation needs to be performed. This can be done in constant time by checking if the first two elements are not in the same order as they should be in the final permutation.
Perform a type 2 operation.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 119 (11900-11999)”