GATE 2025 DA Q.64: solution and answer

GATE 2025 · DAQ.64 · 2 marks · NAT

Consider the following pseudocode.

Create empty stack S
Set x=0, flag=0, sum=0
Push x onto S
while (S is not empty){
   if (flag equals 0){
     Set x = x+1
     Push x onto S}
   if (x equals 8):
     Set flag=1
   if (flag equals 1){
     x = Pop(S)
     if (x is odd):
       Pop(S)
     Set sum = sum + x}
}
Output sum

The value of sum output by a program executing the above pseudocode is ______________ (Answer in integer)

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The program outputs $sum = 24$ .

Official answer: 24Source: Official answer key, GATE 2025 DA (IIT Roorkee)

Initially the stack is $S = [0]$ (bottom to top), with $x = 0$ , $flag = 0$ , $sum = 0$ .
While $flag = 0$ , each pass of the loop executes x = x+1 and pushes the new $x$ . Nothing is popped. After pass 8, $x = 8$ and $S = [0, 1, 2, \dots, 8]$ . The test x equals 8 is now true, so flag=1.
In that same pass 8 the flag equals 1 block also runs. x = Pop(S) gives $x = 8$ and $S = [0, \dots, 7]$ . Since 8 is even there is no second pop, and $sum = 0 + 8 = 8$ .
From pass 9 on, $flag = 1$ , so the first if never runs again and nothing is pushed. The test x equals 8 may set flag=1 again, which changes nothing. Each pass pops once into $x$ , and pops a second element (discarded) if that $x$ is odd. The popped $x$ is the value added to sum.
Pass 9: pop 7 (odd), so also pop 6. $sum = 8 + 7 = 15$ , $S = [0, \dots, 5]$ .
Pass 10: pop 5 (odd), so also pop 4. $sum = 15 + 5 = 20$ , $S = [0, 1, 2, 3]$ .
Pass 11: pop 3 (odd), so also pop 2. $sum = 20 + 3 = 23$ , $S = [0, 1]$ .
Pass 12: pop 1 (odd), so also pop 0. $sum = 23 + 1 = 24$ , and $S$ is empty, so the loop ends.
Output: $sum = 8 + 7 + 5 + 3 + 1 = 24$ .

KEY IDEA

Split the run into two phases. First, with $flag = 0$ , the stack fills with $0, 1, \dots, 8$ . Then with $flag = 1$ , each pass pops one element and also discards the next one whenever the popped value is odd. Note that the pass in which $x$ reaches 8 also performs the first pop, because the flag equals 1 test comes after flag is set in the same pass.

WATCH OUT FOR

Treating the pass that sets flag=1 as a pure push pass and so skipping the pop of 8. That leaves 8 out of the sum and gives 16 instead of 24. Another slip is to forget that the second pop after an odd value discards the next element without adding it to the sum.

From the GATE 2025 DA paper. Every question of this paper · Download the full paper · All 13 Linear structures questions, with notes

GATE 2025 DA Q.64: solution and answer

Answer and solution

More Linear structures questions