Let A be an array containing integer values. The distance of A is defined as the minimum number of e

Q: What is GATE-CS?

GATE-CS is a competitive examination conducted in India. This question is from the 2024 GATE-CS Algorithm paper.

Q: How can I prepare for GATE-CS Algorithm?

To prepare for GATE-CS Algorithm, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2024 question covers Searching topic.

Q: What is the difficulty level of this question?

This GATE-CS 2024 Algorithm question has a medium difficulty level and is marked as an important question.

Q: Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

Question

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 ___________

Accepted Answer

Answer: 3Concept -- Longest Non-Decreasing Subsequence (LIS variant): The distance is n minus the length of the longest non-decreasing subsequence (LNDS), because we keep the LNDS elements in place and replace all others.Array: [2, 5, 3, 1, 4, 2, 6]. n = 7.Find the longest non-decreasing subsequence. Some candidates: 2, 3, 4, 6 (length 4); 2, 5, 6 (length 3); 1, 2, 6 (length 3); 2, 3, 4, 6 -- verify: indices 0(2), 2(3), 4(4), 6(6). Yes, 2  2). 2, 5, 6 -- only 3. 2, 3, 4, 6 seems to be the longest at length 4.Distance = 7 - 4 = 3.

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 ___________

Master GATE-CS with Our Test Series

More Questions from Searching

Frequently Asked Questions

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 ___________

Master GATE-CS with Our Test Series

More Questions from Searching

Frequently Asked Questions