GATE 2024 CS2 Q.42: solution and answer

GATE 2024 · CS2Q.42 · 2 marks · MCQ

Consider an array X that contains n positive integers. A subarray of X is defined to be a sequence of array locations with consecutive indices.

The C code snippet given below has been written to compute the length of the longest subarray of X that contains at most two distinct integers. The code has two missing expressions labelled (P) and (Q).

int first=0, second=0, len1=0, len2=0, maxlen=0;
for (int i=0; i < n; i++) {
  if (X[i] == first) {
    len2++; len1++;
  } else if (X[i] == second) {
    len2++;
    len1 = (P) ;
    second = first;
  } else {
    len2 = (Q) ;
    len1 = 1; second = first;
  }
  if (len2 > maxlen) {
    maxlen = len2;
  }
  first = X[i];
}

Which one of the following options gives the CORRECT missing expressions?

(Hint: At the end of the i-th iteration, the value of len1 is the length of the longest subarray ending with X[i] that contains all equal values, and len2 is the length of the longest subarray ending with X[i] that contains at most two distinct values.)

(A)
(P) len1+1 (Q) len2+1
(B)
(P) 1 (Q) len1+1
(C)
(P) 1 (Q) len2+1
(D)
(P) len2+1 (Q) len1+1

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The correct missing expressions are (P) = 1 and (Q) = len1 + 1, which is option B.

Official answer: BSource: Official answer key, GATE 2024 CS2 (IISc Bengaluru)

Invariant to maintain: len1 = length of the run of equal values ending at X[i]; len2 = length of the longest at-most-two-distinct-value subarray ending at X[i].
(P) branch: X[i] == second and (since the first if failed) X[i] != first = X[i-1]. So X[i] differs from its immediate predecessor, meaning the equal-value run ending at i has length exactly 1 — hence (P) = 1 (not len1+1, which would double-count).
(Q) branch: X[i] differs from both first and second, i.e. a brand-new third distinct value appears. The longest at-most-two-distinct subarray ending at i must drop the oldest of the two previous values and keep only the maximal run of the immediately preceding value (length len1) plus the current new element — giving exactly 2 distinct values and length len1+1. So (Q) = len1+1.
Full trace with X = [5,5,5,3,5,5] (n=6), using (P)=1, (Q)=len1+1: i=0 (else branch, first/second both start at 0 which never matches a positive integer): len2=1,len1=1,first=5. i=1,2 (X[i]==first=5): len2=2,3; len1=2,3. i=3 (X=3, else branch): len2=len1+1=4, len1=1, second=5, first=3. i=4 (X=5==second): len2=5, len1=(P)=1, second=3, first=5. i=5 (X=5==first): len2=6, len1=2. maxlen reaches 6 = n, matching that the whole array uses only values {5,3} — 2 distinct values throughout.
Cross-check with alternating X = [1,2,1,2,1,2] (2 distinct values throughout, so maxlen must reach n=6): with (P)=1, (Q)=len1+1 the len2 sequence is 1,2,3,4,5,6 — correctly reaching n.
Testing (Q)=len2+1 (option C) on the same alternating trace gives len2 growing 1,2,4,8,... which overshoots n=6, violating the invariant and eliminating C (and by the (P) check, D and A are eliminated too since they don't use (P)=1).
Only option B — (P)=1, (Q)=len1+1 — satisfies both traces and the stated invariant.

KEY IDEA

Track two lengths in parallel — len1 for the run of the single most-recent value, len2 for the window of at most two distinct values — and derive each missing expression from what changes about the "previous" value when the current element repeats the second-to-last distinct value (P) versus introduces a brand-new third value (Q).

WATCH OUT FOR

Assuming len1 always just increments (using len1+1 for (P)) instead of recognizing that hitting the else if (X[i]==second) branch means X[i] is different from its immediate predecessor, so the single-value run must restart at 1; symmetrically, mistakenly using len2+1 for (Q) double-counts the old two-distinct window instead of correctly discarding the older of the two previous values and keeping only the immediately preceding run (len1) plus the new element.

From the GATE 2024 CS2 paper. Every question of this paper · Download the full paper · All 8 Design techniques questions, with notes

GATE 2024 CS2 Q.42: solution and answer

Answer and solution

More Design techniques questions