made easy test

Question

The number of permutations can be obtained in the output using stack assuming that input contains elements 1, 2, 3, 4, 5, 6 in any order such that 3 will poped out from stack at 3rd position are _______ (assume one element enter in stack only one time).

Comments

5!?

---

How ?

---

3 should be inserted after inserting 3 elements at 4th position into the stack so that it will be the third element to be popped. This can be done in 5! ways, keeping 4th position out of 6 fixed and shuffling other 5 positions with 5 elements.

---

@balchandar reddy san

 what would be the answer if we inserted the elements in ascending order i.e.. 1,2,3,4,5,6 order ? 

---

If inputs arrive in ascending order, then there is only 1 permutation that is possible right satisfying the condition given in the question?

---

We want 3 to pop at 3rd position. If input if given in ascending order 1,2,3,4,5,6 then 4 will be popped at 3rd position.

---

In that case, it will be 0 because the 3rd element to be popped will be 4.

---

In order to pop 3 at 3rd position, we can insert 1,2,3,4,5 in order and then pop 5,4,3 in this order. Finally we can insert 6. So the final stack contents will be 1,2,6.So there is only one way possible, isnt it?

---

Input can be any permutation of 1,2,3,4,5,6 then why restrict it to ascending order?

---

gauravky

cant it occur in the way that I just mentioned in the previous comment?

---

No. The question is saying the stack already has 1,2,3,4,5,6 in any order. How many permutations of the output has 3 as 3rd popped element.

Fix the 3rd element from the top in the stack as 3. Rest 5, can be placed in 5! ways.

---

gauravkc

what would be the answer if we inserted the elements in ascending order i.e.. 1,2,3,4,5,6 order ? 

I was speaking about this question..

---

@Somoshree Datta 5 Even considering your case, there will be 1 more possibility as you can push 1,2,3,4 in order and then pop 4 then add 5 and then pop 5 then you can pop 3.

---

Then it depends I think.

The qn states elements are already in stack. If the stack has 1,2,3,4,5,6 then 0 ways as 3rd element will be 4.

But if the stack is empty and we are free to perform push pops in any order, then 1 way as you said.

Woah! Didn't think of that @balchandar reddy san

---

balchandar reddy san

yes,so there are 2 permutations possible right?

---

gauravkc

where is it said that elements are already present in the stack?

---

The permutation in stack will be same as permutation of input in given qn.

Here we are altering the sequence of push pops. In modified qn.

---

@Somoshree Datta 5

Yes 2

---

@Somoshree Datta 5 

push 1 , 2

pop 2 .. 

then push 3 , 4

pop 4 

pop 3  . 3 is popped at third position

---

Push 1 pop 1

push 2 pop 2

push 3 pop 3 :p

---

@gauravkc

there can be many sequence like that for somoshee question... but the answer to the actual question is 5! right 

---

Yes.

---

Ooo.. :p there are many such permutations possible.. Then how many are possible for that question??

---

I'm not sure

Is it 42 ???

---

Can u post your approach? 42 seems to be a big number though.

---

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

 

We can did such types of questions by Catalan number 

But it's given that 

 3 will poped out from stack at 3rd position 

Therefore 3rd position is fixed and we arranged the 5 numbers

By 2n Cn / (n+1)  where n = 5 

 

---

@balchandar reddy san

@Somoshree Datta 5

@Magma

My approch, not sure if its correct.

so given we need to pop element '3' in the 3rd position.

_ _ 3 _ _ _

the only possible numbers in the first 2 slots is 1,2 or 2,1 or 4,5 or 5,4.

consider the case where its 1,2

so we have 1 2 3 _ _ _

the 3 blank spaces can be filled with 

4,5,6

4,6,5

5,4,6

5,6,4

6,5,4

the same possibilities are possible for 2,1 aswell.

now consider the case where 4,5 is filled in the first 2 blank spaces.

4 5 3 _ _ _

the leftover 3 blank space can be filled in

2,1,6

6,2,1

the same possibilities are possible for 5,4 aswell.

hence total possibilities are 5+5+2+2 = 14.

---

But why @pream sagar is not telling that that's the answer given ??

 

---

ans is 5! given by madeeasy

---

@OneZero

in the question given elements can be inserted in any order , but u r taking it only in increasing order.

if elements are inserted in any order then it will be 5!

---

what would be the answer if we inserted the elements in ascending order i.e.. 1,2,3,4,5,6 order ? 

i asked this question before, this answer is for the above question. 

---

@OneZero

take this case push 1 , pop 1

push 2 , push 3 , push 4 ..   pop 4 , pop 3

so first two positions are 14 

 

---

Yes, you are right, my answer is wrong.

Answer 1

NOS of permutation is 120.