GATE CS 2024 Set 2 Q.42: Dynamic Programming

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.)

(P) len1+1 (Q) len2+1

(P) 1 (Q) len1+1

(P) 1 (Q) len2+1

(P) len2+1 (Q) len1+1

Official answer and solution

Official answer: B
From: Official GATE 2024 answer key

Solution

Use the loop invariant for len1 (length of the trailing run of first = X[i-1]) and len2 (length of the longest two-value suffix ending at X[i]).

At the start of the i-th iteration (before first = X[i] at the bottom of the loop), first holds X[i-1], len1 is the length of the contiguous block of elements equal to first ending at i - 1, and second holds the other distinct value immediately preceding that block:

Expression (P) (else if (X[i] == second)): Since X[i] != first, a new contiguous run of X[i] begins at index i. Thus the length of the longest subarray ending at X[i] with all equal values is len1 = 1, so (P) is 1.
Expression (Q) (else, when X[i] is a new third value): Any subarray ending at X[i] with at most two distinct values can only include X[i] and the immediately preceding contiguous block of first (of length len1), since including any element before that block would introduce second (a third distinct value). Thus len2 = len1 + 1, so (Q) is len1+1.

Final answer

Option (B)

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2024 Computer Science and Information Technology - Set 2 (CS2)
Question: 42 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source