GATE CS 2024 Set 2 — Question 42

MCQ+2 / -0.67HardArrays & Strings in CC ProgrammingProgramming & Data StructuresArray Operations (1D, 2D)Arrays & Strings

Programming & Data Structures → Arrays & Strings → Array Operations (1D, 2D)

Last updated 20 August 2026

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)

int first=0, second=0, len1=0, len2=0, maxlen=0;
for (int i=0; i &lt; 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 &gt; 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

Correct answer

(B) (P) 1 (Q) len1+1

Solution

The code maintains two lengths:

1.len1: The length of the current run of identical elements ending at

X[i]

2.len2: The length of the current subarray ending at

X[i]

containing at most two distinct elements.

Let's analyze the cases in the loop:

Case 1: $X[i] == first$

The current element is the same as the previous one. Both len1 and len2 increment by 1. This is correctly handled in the code.

Case 2: $X[i] == second$

The current element is different from the previous one (

first

) but matches the other distinct element in the current window (

second

len2 increments by 1 because it's still within the two-distinct-element limit.
Since $X[i] \neq first$ , a new run of identical elements starts with $X[i]$ . Thus, len1 must be reset to 1. So, $(P) = 1$ .
The variable second is updated to the previous first to prepare for the next iteration.
Case 3: $X[i]$ is a new distinct element

The current element is neither first nor second. To maintain at most two distinct elements, the new window must start from the beginning of the previous run of identical elements (first) and include the current element

X[i]

The length of this new window is the count of the previous identical elements (len1) plus the current element. Thus, len2 = len1 + 1. So, $(Q) = len1 + 1$ .
len1 is reset to 1 for the new run starting at $X[i]$ .

Comparing with the options,

(P) = 1

and

(Q) = len1 + 1

corresponds to option (B).

GATE CS 2024 Set 2 — Question 42

Question

Correct answer

Solution

More questions on Arrays & Strings