GATE 2024 CS2 Q.35: solution and answer

GATE 2024 · CS2Q.35 · 1 mark · NAT

Let $A$ be an array containing integer values. The distance of $A$ is defined as the minimum number of elements in $A$ that must be replaced with another integer so that the resulting array is sorted in non-decreasing order. The distance of the array $[2, 5, 3, 1, 4, 2, 6]$ is ____________.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The distance of the array is 3.

Official answer: 3Source: Official answer key, GATE 2024 CS2 (IISc Bengaluru)

Reformulate the problem: the elements that are NOT replaced must already appear in non-decreasing order among themselves (as a subsequence), because every replaced position can be filled with any value needed to bridge the gaps and keep the whole array non-decreasing.
Therefore the minimum number of replacements equals $n$ minus the length of the Longest Non-Decreasing Subsequence (LNDS) of the array.
Let $a = [2, 5, 3, 1, 4, 2, 6]$ (1-indexed), so $n = 7$ .
Define $L (i)$ = length of the LNDS ending at index $i$ : $L (i) = 1 + max {L (j) : j < i, a [j] \leq a [i]}$ , or $L (i) = 1$ if no such $j$ exists.
$L (1) = 1$ for $a_{1} = 2$ . $L (2) = 2$ for $a_{2} = 5$ (using $a_{1} = 2$ ). $L (3) = 2$ for $a_{3} = 3$ (using $a_{1} = 2$ ). $L (4) = 1$ for $a_{4} = 1$ (no earlier element $\leq 1$ ).
$L (5)$ for $a_{5} = 4$ : eligible predecessors ( $\leq 4$ ) are $a_{1} = 2 (L = 1)$ , $a_{3} = 3 (L = 2)$ , $a_{4} = 1 (L = 1)$ ; taking the maximum gives $L (5) = 1 + 2 = 3$ (subsequence $2, 3, 4$ ).
$L (6)$ for $a_{6} = 2$ : eligible predecessors ( $\leq 2$ ) are $a_{1} = 2 (L = 1)$ , $a_{4} = 1 (L = 1)$ ; so $L (6) = 1 + 1 = 2$ .
$L (7)$ for $a_{7} = 6$ : all earlier elements are $\leq 6$ , so the eligible set is everything; the maximum among $L (1), \dots, L (6) = 1, 2, 2, 1, 3, 2$ is $3$ (at $i = 5$ ), giving $L (7) = 1 + 3 = 4$ (subsequence $2, 3, 4, 6$ at indices $1, 3, 5, 7$ ).
The length of the LNDS is $max_{i} L (i) = 4$ .
Distance $= n - LNDS = 7 - 4 = 3$ . Check: keeping positions $1, 3, 5, 7$ (values $2, 3, 4, 6$ ) and replacing positions $2, 4, 6$ with, say, $2, 3, 3, 4, 4, 4, 6$ gives a valid non-decreasing array using exactly $3$ replacements, and no non-decreasing subsequence of $a$ has length greater than $4$ , so $3$ is indeed the minimum.

KEY IDEA

Minimum replacements to make an array non-decreasing = $n$ − (length of the Longest Non-Decreasing Subsequence), because the untouched elements must themselves already form a non-decreasing subsequence, and any gaps left by replaced elements can always be filled with values that bridge them.

WATCH OUT FOR

Comparing the array with its sorted version, [1, 2, 2, 3, 4, 5, 6], and counting the positions that differ gives 5, because only positions 5 and 7 already match. The elements kept unchanged need only be in non-decreasing order among themselves, not in their final sorted positions, so the distance is $n$ minus the length of the longest non-decreasing subsequence: $7 - 4 = 3$ .

From the GATE 2024 CS2 paper. Every question of this paper · Download the full paper · All 8 Design techniques questions, with notes

GATE 2024 CS2 Q.35: solution and answer

Answer and solution

More Design techniques questions