Computer Sciences > Gate 2024 Set-2 > Thread
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 (𝑄).
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     (𝑃) 1
B
(𝑃) 1             (𝑃) len2+1
C
(𝑄) len2+1   (𝑄) len1+1
D
(𝑄) len2+1   (𝑄) len1+1

Correct : c

Explanation:
Let us analyze the logic using the hint provided: β€’ len1 tracks the length of the longest subarray ending at X[i] containing all equal elements (a sequence of the current active element). β€’ len2 tracks the length of the longest subarray ending at X[i] containing at most two distinct elements. At the very end of every iteration, the statement first = X[i]; runs. This means first always holds the element processed in the previous iteration, and second holds the distinct element seen right before that continuous sequence of first broke.
1. Finding Expression (P): β€’ This block executes when X[i] == second.
β€’ Since X[i] matches second, the old continuous sequence of first is broken.
β€’ The new continuous sequence of equal elements now consists of the old second element plus the current X[i].
β€’ Since second was located adjacent to the continuous block of first, the new continuous sequence length becomes the count of the previous continuous block (len1) plus 1 for the current element.
    (P) = len1 + 1
2. Finding Expression (Q): β€’ This block executes when X[i] is completely new (does not match first or second).
β€’ Since it is a third distinct element, we must drop the older distinct element (second) to keep at most two distinct elements.
β€’ The new valid subarray can only consist of the most recent continuous block of equal elements (first) and the current new element X[i].
β€’ Therefore, the new total length len2 becomes the length of the continuous block of first (which is len1) plus 1 for the current element.
    (Q) = len1 + 1
Conclusion: Both (P) and (Q) must be len1 + 1, matching option (c).

Similar Questions

Consider a multi-threaded program with two threads T1 and T2. The threads share two semaphores: s1 (initialized to 1) and s2 (initialized to 0). The threads a...
#842 MCQ
Consider the following expression: π‘₯[𝑖]=(𝑝+π‘Ÿ)βˆ—βˆ’π‘ [𝑖]+𝑒/𝑀. The following sequence shows the list of triples representing the given expression, with entries mi...
#843 MCQ
Let 𝑀 be the 5-state NFA with πœ–-transitions shown in the diagram below. Which one of the following regular expressions represents the language accepted...
#845 MCQ

Related Topics

No tags found

Unique Visitor Count

Total Unique Visitors

Loading......