GATE CSE 2024 | Set 2 | Question: 25

Question

Let $\text{A}$ be an array containing integer values. The distance of $\text{A}$ is defined as the minimum number of elements in $\text{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 ___________.

Answer 1

Given array: [2, 5, 3, 1, 4, 2, 6]

Indices:   0  1  2  3  4  5  6
Values:    2  5  3  1  4  2  6

The array with sorted indices:

Indices:   0  1  2  3  4  5  6
Values:    2  2  3  3  4  4  6
 

Number of elements out of order: 3

Answer 2

Answer is 3.

Non decreasing means the resultant array should be increasing but not necessary strictly increasing.

Assume 0th order indexing.

Swap 5 and 2( at 5th index)

Swap 2(at 0th index ) and 1

Swap 3 and 2 ( at 3rd index)

So total 3 swaps are needed hence the minimum distance is 3.