Skip to content
GATEiit

GATE CSE 2024 Session 2 Q35: Minimum replacements to make an array non-decreasing

Question

Let AA be an array containing integer values. The distance of AA is defined as the minimum number of elements in AA 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][2, 5, 3, 1, 4, 2, 6] is ___________

Try it: numerical answer: type the value

Numerical answer. No negative marking.
Show answer and explanation

Answer: 3 (official GATE 2024 final answer key)

Concept used: Elements kept unchanged must form a non-decreasing subsequence, so distance = nn − longest non-decreasing subsequence.

First step: Find the longest non-decreasing subsequence of [2,5,3,1,4,2,6][2, 5, 3, 1, 4, 2, 6], for example 2,3,4,62, 3, 4, 6.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2024 Session 2 CS question paper and final answer key, organised by IISc Bangalore. Question paper · Answer key

More Algorithms PYQs

PracticePractise Algorithms questions →Full paperAll GATE CSE 2024 Session 2 questions →