in DS
529 views
5 votes
5 votes
Consider a stack with 100 elements present. Suppose in a scenario, we are required to remove the first inserted element in it, which is done by POP operations followed by PUSH operations with intermediate elements temporarily being saved in an array. After $10$ such removals, without anyother intermediate PUSH/POP operations, total number of PUSH operations required is ______
in DS
by
529 views

1 comment

What question says is

100 elements are already present in the stack. Say in the bottom up manner from 1,2,3, . . . 100.

Now to remove 1 we need to do 100 pop operation and then save remaining 99 elements to temporary location (as not specified to save it to another stack) and then again push those 99 elements to stack again.

So now the stack has elements 2,3,4,. . .,100. Now to remove 2 we again follow the same procedure so we will end up with 99 pop operations followed by 98 push operations.

Continuing this to 10 times we will get no of $\textbf{PUSH = }$ 99 + 98 + . . . + 90 = 945
1
1

1 Answer

8 votes
8 votes
Best answer
Initially we do 100 POP followed by 99 PUSH.

For 10 such operations we would do

$99 + 98 + 97+96+95+94+93+92+91+90 = 900+45 = 945$ PUSH operations.
selected by
by

8 Comments

What if I do in this manner,

first POP 99 elements and PUSH it onto temporarary stack.

Now, if we POP first 9 elemts from this temporary stack then it will do 10 removals which we require and then PUSH remaining 90 elements onto our original STACK.

so total 90 PUSH operaions, is it?

1
1
Questions says we did "10 such removals" - so they must have happened individually. Not like we want to remove 10 elements at once.
1
1
ok..i am overthinking to make t optimal! :-)
1
1
After 10 removals!!

Shouldn't we count the case 90+89+88+---+2+1 ?
0
0
why not counting the push reqd to again put the elements from temporary array to stack?
1
1
Why add 45
0
0
90*10 + (0+1+2+3+4+5+6+7+8+9)=945
0
0
I could not understand the question itself. Can someone please explain
0
0
Answer:

Related questions