The GATE Grind

GATE 2024 CS (CS2) – Question 42

Algorithms · Dynamic Programming · 2 marks · Multiple choice

Consider an array X of n positive integers. The C code below computes the length of the longest subarray of X containing at most two distinct integers, with two missing expressions (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];
}

Hint: at the end of the i-th iteration, len1 is the length of the longest subarray ending with X[i] with all equal values, and len2 is the length of the longest subarray ending with X[i] with at most two distinct values. Which option gives the CORRECT missing expressions?

  1. (P) len1+1 (Q) len2+1
  2. (P) 1 (Q) len1+1
  3. (P) 1 (Q) len2+1
  4. (P) len2+1 (Q) len1+1

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) (P) 1 (Q) len1+1

Explanation

When X[i] equals second, the run of equal values restarts at 1 (P = 1). When X[i] is a new value, the new two-distinct subarray is the previous equal-run plus the new element: len2 = len1 + 1 (Q).