GATE CS 2025 Set 2 | Question 20

MCQ · 1 mark · −0.33

Consider an unordered list of \(N\) distinct integers.

What is the minimum number of element comparisons required to find an integer in the list that is NOT the largest in the list?

  1. Option A: 1 (correct)
  2. Option B: \(N - 1\)
  3. Option C: \(N\)
  4. Option D: \(2N - 1\)

Answer

(A)

Explanation

Pick any two elements and compare them once. Because the integers are distinct, one of them is strictly smaller, and that smaller element cannot be the largest in the list: the other element beats it. So one comparison always suffices.

Zero comparisons cannot work, since without any comparison every element we might pick could still be the maximum. Hence the minimum is 1.

\(N - 1\) comparisons are what it takes to find the largest element itself, which is a different task; the question only asks for some element that is not the largest.

Answer: A