in DS
392 views
3 votes
3 votes
A function $f$ defined on stack of integer satisfies the following properties:

$f(\{\}) = 1$ and

$f(PUSH(S,i)) = \max (f(S),1) * i$ for all stacks $S$ and integer $i$.

If a stack $S$ contains the integers $4, -2, 9$ in order from bottom to top, what is $f(S)$?
in DS
by
392 views

2 Answers

7 votes
7 votes
Best answer
$f$ is defined on a stack and its value changes on a push operation.

Initially $f(S) = 1$ when no element is present.

After first push, 4, $f(S) =\max(1,1) \times 4 = 4$.

After second push, -2, $f(S) = \max(4,1) \times -2 = -8$.

After third push, 9, $f(S) = \max(-8, 1) \times 9 = 9$.
selected by
by

3 Comments

Initially f(S)=1 when stack is empty .rt?
1
1
Thanks. Corrected..
1
1
@Arjun sir,

How can we see that f(S) = 1, its not mentioned in the question.

Also, how have you taken f(S) = max(f(S),1)*i, in the question, its mentioned that f(PUSH(S,i)) = max(f(S),1)*i
1
1
0 votes
0 votes

f({})=1

=> When S is empty, this function value is 1.

We have to push 4, -2 and 9 in this empty stack so that the given stack configuration in the question is achieved.

  • When pushing 4; max (1,1)*4 = 4
    So, f(S) = 4 now.
     
  • When pushing -2; max(4,1)*-2 = -8
    So, f(S) = -8 now.
     
  • When pushing 9; max(-8,1)*9 = 9
    So, f(S) = 9 now.
Answer:

Related questions