GATE CSE
First time here? Checkout the FAQ!
x
+5 votes
151 views

Loading Question

asked in DS by Veteran (10.5k points)   | 151 views
Nice question ..But time taking before arriving at a conclusion.
Yes. The only way i am knowing is by writing all permutations. I want to know if it can be solved by some logic.
In such questions as I said earlier you have to do what is mentioned in the question and solve accordingly.This was the confusion which I had earlier.Let me rectify

1 Answer

+6 votes
Best answer

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

answered by Veteran (66.5k points)  
selected by
Answer is correct. But how do you conclude this formula.??

Try to do with 3  numbers . 

The number of permutation is equal to no. of post-order of binary search tree . since with 3 nodes number of binary search tree are 2nC/ (n+1) .

Of course the formula is correct. But this question is fill in the blank type. Ijust want to know how such conclusion can be obtained.
i already give you hint try with small number then you idea .
It is analogous to balanced parantheses problem with prefix property.Check for it u will get the idea .Only the difference is instead of opening and closing brackets , we are using push and pop here.
Thank you guys.
I dont know who has downvoted my comment and for what reason..It is better to give valid argument also if one is downvoting.

One does not become great by simply downvoting..If one want to show skill , then give legitimate comments ..I have no problem..

But don't do this silly thing..


Top Users May 2017
  1. akash.dinkar12

    3154 Points

  2. pawan kumarln

    1636 Points

  3. sh!va

    1590 Points

  4. Arjun

    1350 Points

  5. Bikram

    1298 Points

  6. Devshree Dubey

    1246 Points

  7. Angkit

    1044 Points

  8. Debashish Deka

    1042 Points

  9. LeenSharma

    880 Points

  10. srestha

    706 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 May 22 - 28
  1. Bikram

    384 Points

  2. pawan kumarln

    262 Points

  3. Ahwan

    236 Points

  4. Arnab Bhadra

    136 Points

  5. LeenSharma

    118 Points


22,770 questions
29,090 answers
65,119 comments
27,635 users