GATE DA 2024 | Question 39

Consider the function computeS(X) whose pseudocode is given below:

computeS(X)
S[1] ← 1
for i ←2 to length(X)
  S[i] ← 1
  if X[i - 1] ≤ X[i]
      S[i] ← S[i] + S[i - 1]
  end if
end for
return S

Which ONE of the following values is returned by the function computeS(X) for \(X = [6, 3, 5, 4, 10]\)?

Option A: [1, 1, 2, 3, 4]
Option B: [1, 1, 2, 3, 3]
Option C: [1, 1, 2, 1, 2] (correct)
Option D: [1, 1, 2, 1, 5]

Answer

(C)

Explanation

\(S[i]\) is the length of the non-decreasing run that ends at position \(i\): it restarts at 1 and adds \(S[i-1]\) only when \(X[i-1] \le X[i]\). With \(X = [6, 3, 5, 4, 10]\), indexed from 1:

\(S[1] = 1\).
\(i = 2\): \(6 \le 3\) is false, so \(S[2] = 1\).
\(i = 3\): \(3 \le 5\), so \(S[3] = 1 + S[2] = 2\).
\(i = 4\): \(5 \le 4\) is false, so \(S[4] = 1\).
\(i = 5\): \(4 \le 10\), so \(S[5] = 1 + S[4] = 2\).

Options A and B miss the restart at the drop from 5 to 4; option D restarts there but then overstates \(S[5]\).

Answer: C