IAE Academy

GATE 2025 CS2 Q.20: solution and answer

GATE 2025 · CS2Q.20 · 1 mark · MCQ

Consider an unordered list of 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. (A)

    1

  2. (B)

  3. (C)

  4. (D)

See the question in the paper
GATE 2025 CS2 question 20Tap to open full size

Answer and solution

ANSWER

The minimum number of element comparisons required is 1 (Option A).

Official answer: ASource: Official answer key, GATE 2025 CS2 (IIT Roorkee)

  1. The task is only to certify that ONE element is not the overall largest — not to find the maximum, the minimum, sort the list, or identify the second-largest.

  2. Pick any two distinct elements x and y from the list (valid since all N integers are distinct and N ≥ 2).

  3. Compare x and y with a single comparison: exactly one of x < y or y < x holds.

  4. The smaller of the two (say x, if x < y) is certified NOT to be the largest element in the whole list, because y is strictly greater than x.

  5. Zero comparisons cannot work: with no information gathered, every element remains a possible candidate for being the largest, so no arbitrary choice can be guaranteed correct.

  6. Hence 1 comparison is both sufficient and necessary — the minimum number of element comparisons required is 1, matching option A.

KEY IDEA

To show an element is not the largest, it is enough to find one element bigger than it: a single comparison between any two elements does that, and the smaller of the two is the answer.

WATCH OUT FOR

Confusing this with "find the maximum" (which needs comparisons) or "find the second largest" (needs comparisons via a tournament). The question only asks for ANY element guaranteed not to be the largest, which is a much weaker requirement solvable in a single comparison.

From the GATE 2025 CS2 paper. Every question of this paper · Download the full paper · All 18 Sorting & hashing questions, with notes

More Sorting & hashing questions