Discussion
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.)
Answer: B
The missing expressions are (P) 1 and (Q) len1+1.
At each step, first holds X[i-1] and second the other value in the current two-value window. If X[i] equals second, it differs from the previous element, so the run of equal values ending at X[i] is X[i] alone: len1 becomes 1, which is (P). The window still has only two values, so len2 grows by one.
If X[i] is a new third value, the longest two-value subarray ending at X[i] is the run of equal values ending at X[i-1] (length len1) followed by X[i], so len2 becomes len1+1, which is (Q). Then len1 resets to 1.
(P) len1+1 would extend a run across a change of value, and (Q) len2+1 would keep three distinct values in the window, so the other options fail.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development