edited by
1,423 views
9 votes
9 votes
An item that is read as input can either be pushed to the stack and later popped and printed or printed directly. Number of print permutations that can be obtained using stack, if the input sequence is $1, 2, 3, 4, 5$ in that order is __________.
edited by

1 Answer

Best answer
10 votes
10 votes

This is a problem whose soltution lies in Catalan number.In this case for any permutation no of pushes >= no of pops for any prefix of permutaion 

So 5th Catalan no is given by :   2nC/ (n+1)

                                          =   10C5 / 6

                                          =   42

Hence the answer to this question should be 42.

Plz refer to the link :

http://math.stackexchange.com/questions/17769/using-one-stack-to-find-number-of-permutations

selected by

Related questions

4 votes
4 votes
2 answers
1
srestha asked Jan 4, 2017
7,549 views
Which of the following permutations can be obtained in the output (in the same order) using a stack assuming that the input is the sequence 5, 7, 8, 4, 6 in that order?a)...
2 votes
2 votes
2 answers
3
jatin khachane 1 asked Dec 1, 2018
1,221 views
My doubt : What should we consider ^ operator as Bitwise XOR ? or Exponentiation