Question

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)\). \begin{verbatim} 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]; } \end{verbatim} Which one of the following options gives the CORRECT missing expressions?

• A. \((P)\) \( \text{len1} + 1 \), \((Q)\) \( \text{len2} + 1 \)
• B. \((P)\) \(1\), \((Q)\) \( \text{len1} + 1 \)
• C. \((P)\) \(1\), \((Q)\) \( \text{len2} + 1 \)
• D. \((P)\) \(\text{len2} + 1\), \((Q)\) \( \text{len1} + 1 \)

Hint:

Carefully track the roles of variables in maintaining properties of subarrays. \(len1\) tracks identical elements, while \(len2\) tracks subarrays with at most two distinct integers.

Answer 1

The Correct Option is B

The goal is to maintain the length of the longest subarray ending at the current index \(i\) with at most two distinct integers. The variables have the following roles:
1. \(len1\): Length of the subarray ending at \(X[i]\) where all elements are equal to \(X[i]\).
2. \(len2\): Length of the subarray ending at \(X[i]\) with at most two distinct integers.
Analysis of (P): When \(X[i] == \text{second}\), \(len1\) must be reset to 1 because this marks the start of a new sequence of identical integers. Thus, \((P) = 1\).
Analysis of (Q): When \(X[i]\) is neither \(first\) nor \(second\), \(len2\) must be updated to include the length of the subarray containing the new two distinct integers. Since the previous \(len1\) represents the length of the contiguous subarray of \(first\), the new \(len2 = \text{len1} + 1\) (the current element \(X[i]\) is added). Thus, \((Q) = \text{len1} + 1\). The correct replacements for \((P)\) and \((Q)\) are: \[ (P) = 1, \quad (Q) = \text{len1} + 1. \] Final Answer: \[ \boxed{\text{(B)}} \]