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 ___________.

Comments

[2 5 3 1 4 2 6] Swap(5 or 2) 

Now [2 2 3 1 4 5 6 ] ---------1

Swap(3 or 1)

     and  [2 2 1 3 4 5 6] --------------2

Swap(2 or 1)

[1 2 2 3 4 5 6]----------3

Thus, the minimum number of elements that must be replaced to sort the array in non-decreasing order is 3.

---

 

 

2 5 3 1 4 2 6

Three elements are not in order we need to 3 replacements 

So read the yellow line carefully

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

Assume  the replacement 2 3 3 4 4 5 6 

 

 

---

A : [ 2,5,3,1,4,2,6 ]

Step 1=> Swap : A[0] <> A[3]        // A[0] = 2, A[3] = 1

A : [ 1,5,3,2,4,2,6 ]       

Step 2=> Swap : A[1] <> A[5]        // A[1] = 5, A[5] = 2

A : [ 1,2,3,2,4,5,6 ]       

Step 3=> Swap : A[2] <> A[3]        // A[2] = 3, A[3] = 2

A : [ 1,2,2,3,4,5,6 ]       

Ans.: Thus, the minimum number of elements that must be replaced to sort the array in non-decreasing order is 3.

Answer 1

To calculate the distance of the array, we need to determine how many elements must be replaced to transform the given array into a sorted, non-decreasing array.

Here’s how we can approach the problem:

1. Find the Longest Increasing Subsequence (LIS): The LIS will represent the largest subset of elements that are already in the correct order.
2. Calculate the distance: The distance will be the number of elements that are not part of the LIS, since those elements would need to be replaced.

Let's apply this to the given array: [2, 5, 3, 1, 4, 2, 6]

Step 1: Find the LIS
The longest increasing subsequence in this array is [2, 3, 4, 6], which has a length of 4.

Step 2: Calculate the distance
The length of the original array is 7. The number of elements that are not part of the LIS is:

Distance = 7 – 4 = 3

Thus, the minimum number of elements that must be replaced to sort the array in non-decreasing order is 3.

Comments

this should be the best answer thanks for the easy way

---

Looking for this .Thank You @Aadil Mugal

Answer 2

Idea:
The question asks for the minimum number of elements that must be replaced so that the array becomes sorted in non-decreasing order.

Do not confuse this with swapping — we are not rearranging positions of elements. We are only changing their values (replacing them) so that the array becomes sorted.

---

If you can find the Longest Non-Decreasing Subsequence (LNDS) of the array, then those elements can stay as they are — and the rest must be replaced.

\[ \text{Original Array:} \] \[ A = [2,\; 5,\; 3,\; 1,\; 4,\; 2,\; 6] \]

\[ \text{Longest Non-Decreasing Subsequence:} \] \[ [\,\boxed{\color{#1a73e8}{2}},\; \color{black}{5},\; \boxed{\color{#1a73e8}{3}},\; \color{black}{1},\; \boxed{\color{#1a73e8}{4}},\; \color{black}{2},\; \boxed{\color{#1a73e8}{6}}\,] \]

Here, the boxed elements 2, 3, 4, 6 (shown in blue) form the longest non-decreasing subsequence. All the black elements are out of order and must be replaced.

\[ \text{Minimum Replacements} = n - \text{Length(LNDS)} = 7 - 4 = 3 \]

\[ \boxed{\text{Answer: Number of elements to be replaced} = 3} \]

Let’s visualize the replacements clearly:

\[ \begin{array}{ccccccc} \text{Original:} & 2 & 5 & 3 & 1 & 4 & 2 & 6 \\[6pt] \text{Replaced:} & 2 & \color{red}{2} & 3 & \color{red}{3} & 4 & \color{red}{4} & 6 \end{array} \]

Here, the values shown in red are the ones that need to be replaced to make the array sorted.

---

Follow-up Question ▼

Let the distance of an array \(A\), denoted as \(D(A)\), be defined as the minimum number of elements that must be replaced (with integers) so that the resulting array becomes sorted in non-decreasing order.

For \[ A = [2, 5, 3, 1, 4, 2, 6] \] if replacements are allowed only with integer values, determine how many distinct final sorted arrays can be obtained after making exactly \(D(A)\) replacements.

Hint ▼

\[ 2,\, \_,\, 3,\, \_,\, 4,\, \_,\, 6 \] \[ [\,2,\, \color{#d32f2f}{x_1},\, 3,\, \color{#1976d2}{x_2},\, 4,\, \color{#388e3c}{x_3},\, 6\,] \] \[ 2 \le \color{#d32f2f}{x_1} \le 3 \le \color{#1976d2}{x_2} \le 4 \le \color{#388e3c}{x_3} \le 6 \] \[ \color{#d32f2f}{x_1} \in \{2,3\}, \quad \color{#1976d2}{x_2} \in \{3,4\}, \quad \color{#388e3c}{x_3} \in \{4,5,6\} \]

Comments

int distance(int A[], int n) {
    int dp[n];
    int i, j, maxLen = 0;

    for (i = 0; i < n; i++) {
        dp[i] = 1;
        for (j = 0; j < i; j++) {
            if (A[j] <= A[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
            }
        }
        if (dp[i] > maxLen)
            maxLen = dp[i];
    }

    return n - maxLen;
}

 

---

A walking W

---

What is dp ? Also, is dp initialised at all eg. when i = 0 , j = 1 what is dp[j] ?

Answer 3

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.

Comments

I did the same swapping, but others are saying replacing with other integers is also ok

Answer 4

Here, 

arr = {2, 5, 3, 1, 4,  2, 6}

As per given in the Question " The distance of is defined as the minimum number of elements in that must be replaced with another integer so that the resulting array is sorted in non-decreasing order. "

So accordingly from the arr. {5, 1, 2} can be replaced with another integer such that '5 with 2 or 3', '1 with 3 or 4', '2 with 4 or 5 or 6'.

Distance = minimum number of elements in that must be replaced with another integer

Minimum distance = 3

Answer 5

how is this ?

Comments

Can we say like this ??

Selection sort takes less swaps compared to any other algorithms so through selection sort we can get 3 swaps !!