Consider an array X that contains n positive integers. A subarray of X is…
2024
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 (𝑃) and (𝑄).
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 = (𝑃) ;
second = first;
} else {
len2 = (𝑄) ;
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.
(𝑃) len1+1 (𝑄) len2+1
- B.
(𝑃) 1 (𝑄) len1+1
- C.
(𝑃) 1 (𝑄) len2+1
- D.
(𝑃) len2+1 (𝑄) len1+1
Attempted by 39 students.
Show answer & explanation
Correct answer: B
Key invariants: len1 is the length of the longest suffix ending at the current index that consists of identical values; len2 is the length of the longest suffix ending at the current index that contains at most two distinct values.
If the current element equals the most recent value (first), both len1 and len2 extend by 1 because the trailing run of identical values grows and the two-value suffix also grows.
If the current element equals the other stored value (second):
• len2 increments by 1 because the two-value suffix continues to include these two values.
• len1 becomes 1 because the previous element (first) was a different value, so the consecutive run of the current value at the end has length exactly 1.
If the current element is a new third distinct value:
• The new two-value suffix consists of the previous run of identical values (length len1) followed by the new element, so len2 must be set to len1 + 1.
• len1 is set to 1 because the new value starts a fresh run of identical values.
Therefore the correct missing expressions are:
(P) = 1
(Q) = len1 + 1
These updates maintain the intended invariants and ensure len2 always reflects the length of the longest suffix with at most two distinct values.
A video solution is available for this question — log in and enroll to watch it.