GATE CS 2025 Set 2 Q.20: Searching and Sorting Algorithms

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$

$N - 1$

$N$

$2N - 1$

Official answer and solution

Solution

Compare any two elements in the list and pick the smaller one.

Since all $N$ integers are distinct (assuming $N \ge 2$ ), take any two elements $a$ and $b$ from the list and perform $1$ comparison:

If $a < b$ , then $a$ is strictly smaller than $b$ , so $a$ cannot be the largest element in the list.
If $b < a$ , then $b$ cannot be the largest element in the list.

Thus, $1$ comparison always suffices.

Final answer

Option (A)

Common trap

Misreading the question as finding the second-largest or smallest element.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Paper: GATE 2025 Computer Science and Information Technology - Session 2 (CS2)
Question: 20 of 65
Section: Computer Science and Information Technology

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.