The Gateway to Computer Science Excellence
0 votes
85 views
Consider a single array $A\left [ 0...........(n-1) \right ]$ is used to implement two stacks. Two stacks grows from opposite end of the array. Variable  $top_{1}$ and $top_{2}$ points to the location of the topmost elements in each of the stacks with initial values of $-1$ and $n$ respectively and $top_{1}<top_{2}$ always. If  certain push and pop operations are performed in either end, then which of the following represents the number of elements are present in the array at any time?

$A)n-top_{2}+top_{1}$

$B)n+1-top_{2}+top_{1}$
in DS by Veteran (119k points) | 85 views

2 Answers

+2 votes
Best answer

Ans is B

Initially the array must be empty that is, it must contain 0 number of elements. Now we are given that top 1 = -1 and top2= n

when no elements are inserted the 2 pointers remain in their same location, i.e. -1 and n

now putting these values in equation a and we get

a) n-top2+top1

= n-n+(-1)

= -1

b) n+1−top2+top1

 = n+1-n-1

=0

As we all know initially the elements in the array is 0. therefore b is the ans.. :)

by Active (3.6k points)
selected by
0

@Hirak

array is from $A\left [ 0,....(n-1) \right ]$

rt?

Then how r u taking top1=-1 and top2=n??

0
It is given in the question itself that top1 and top2 are assigned value -1 and n initially when the array is empty..

Once we insert element on both the sides their values will be incremented and decremented to 0 and n-1 respectively, initially they are -1 and n suggesting that they do not point to any location at all..
0

ok

But , see the question again

It is asking "number of elements are present in the array at any time"

is that mean anytime stack contains $0$ element?

0
Suppose take a situation

A stack contains $8$ elements

and it is array location $A\left [ 0,....,7 \right ]$

And Stack1 contains

$A\left [ 0 \right ]=x$,$A\left [ 1 \right ]=y$,$A\left [ 2 \right ]=z$

Stack2 contains

$A\left [ 5 \right ]=u$,$A\left [ 6 \right ]=v$, $A\left [ 7 \right ]=w$

Now apply the formula $B)$

According to formula

$n+1-top2+top1=8+1-5+2=6$

Now, that is not correct
right?

because, stack contains only 6 elements
+1

Initially stack contains 0 element and i have used my test case for the same.. if i insert 2 elements now one from top1 and another from top2 the value of top1 becomes 0 and value of top2 becomes n-1

now putting these values in b) n+1−top2+top1 we get n+1-(n-1)+1 = 2 i.e. there are 2 elements in the array..

so it is clear that formula b is the right answer for ANY time..

+1

yes, My bad

Got the logic.

In my example

There is top1 is in a[2], and top1 is in a[5]

So, gap between  in this array is 2 elements , i.e. a[3] and a[4].

But when we actually subtracting , we got 5-2=3 element 

To cancel out that extra 1 we  have to subtract it from (n+1) elements

And thus got total elements

Thanks .

–1 vote
Answer is B.
by (21 points)
0

@sagar2405 explain plz

Related questions

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
50,737 questions
57,391 answers
198,591 comments
105,442 users