The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+3 votes
203 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 (12.4k points) | 203 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 (27.6k points)
edited
Total 16 sequences are possible

1 2 3 5 4 6

1 2 3 6 5 4

1 2 3 4 5 6

1 2 3 5 6 4

1 2 3 4 6 5

2 1 3 5 4 6

2 1 3 4 5 6

2 1 3 6 5 4

2 1 3 5 6 4

2 1 3 4 6 5

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

Correct me if i am wrong
yes you're partially correct like me. i will update my answer! why didn't you consider 123564 or 213564?
ok now it became 14
Why is it not 120 ? First three elements can be any of the 5 excluding 3 and can be chosen in 10 ways, after permutting these 3 we get 60 ways. Now the top 2 elements can be permutted in remaining 2 ways. So total number of inputs and thus the output possible 60*2 = 120.
it's an assumption that in this question,  given sequence of input will be followed. @xylene
It is given that input is 1,2,3,4,5,6 and it's not mentioned that this is the sequence.  However, if you consider that answer will be 14.
if sequence is not followed , then answer will be $5!=120$
@nikunj , @manu00x

I think these two are also a valid sequence.

123465

213465
@hemant yes these two are also possible.
@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


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

28,946 questions
36,792 answers
91,068 comments
34,689 users