GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
130 views
How many permutations can be obtained in the output using a stack assuming that the input 1,2,3,4,5,6 such that 3 will be popped out from stack at 3rd position ?
asked in Programming by Veteran (11.9k points)   | 130 views

1 Answer

+3 votes

Case 1:
Push 1, pop 1
push 2, pop 2
push 3, pop 3

Case 2:
push 1
Push 2, Pop 2
Pop 1
push 3, pop 3


As we can see there 2 possibilities before 3(1, 2 and 2, 1), and there will be 4 possibilities after 3  (456, 546, and 564, 654,465).
so far we got 10 sequences.
Remaining 16 will be as follows:

4 5 3 2 1 6
4 5 3 2 6 1
4 5 3 6 2 1
5 4 3 2 6 1
5 4 3 6 2 1
5 4 3 2 1 6

143256

143265

143526

143562

143652

243156

243165

243516

243561

243651

Hence, there total 26 sequences possible.

answered by Veteran (11.1k points)  
edited by
@mannu00x @hemant

ok now became 16

i think there is no such procedure we should follow we have to do it manually and hence it is time consuming so i think they will not ask more then 6 (just an assumption)

if there is any pattern please let me know.
120 it should be i guess

@manu00x

there will be total of 16+10 =26

16 you have already written, 10 more with prefix(143 and 243) are

143256

143265

143526

143562

143652

243156

243165

243516

243561

243651

can u please tell why 120 is wrong
@A_I_$_h  i think you are looking this question as a permutation combination question in which 3 is fixed and 5 slots are empty and we have 5 choices to fill it hence 5!(5 factorial) but stack property should be preserved in this question

for Example:

in your 5! there must be a string 6 5 3 2 1 4 which is not possible in stack so i think your approach don't fit here

correct me if i am wrong


Top Users Sep 2017
  1. Habibkhan

    6960 Points

  2. Warrior

    2424 Points

  3. Arjun

    2358 Points

  4. rishu_darkshadow

    2136 Points

  5. A_i_$_h

    2004 Points

  6. nikunj

    1980 Points

  7. manu00x

    1750 Points

  8. makhdoom ghaya

    1750 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points


26,059 questions
33,665 answers
79,739 comments
31,078 users