GATE CS 2024 Set 2 | Question 35
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 ___________
Explanation
Answer: 3
The elements that are not replaced keep their values and positions, so they must already form a non-decreasing subsequence. Conversely, any kept non-decreasing subsequence works: every other element can be replaced by a value between its kept neighbours, since equal values are allowed. So the distance is the array length minus the length of the longest non-decreasing subsequence.
In \([2, 5, 3, 1, 4, 2, 6]\) the longest one is \(2, 3, 4, 6\), of length 4; no subsequence of length 5 is non-decreasing. Replacing the other three elements (5, 1 and 2) by, say, 3, 4 and 5 gives \([2, 3, 3, 4, 4, 5, 6]\).
Distance \(= 7 - 4 = 3\).
Answer: 3