Consider an unordered list of 𝑁 distinct integers. What is the minimum number…
2025
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?
- A.
1
- B.
𝑁 − 1
- C.
𝑁
- D.
2𝑁 − 1
Attempted by 231 students.
Show answer & explanation
Correct answer: A
Answer: 1 — one comparison is sufficient to find an element that is not the largest (for N ≥ 2).
Why one comparison is sufficient:
Pick any two elements and compare them. The smaller of the two cannot be the largest in the whole list, so it is a valid non-largest element.
Why zero comparisons are not sufficient:
With no comparisons you must choose an element without information. That chosen element might be the largest, so you cannot guarantee correctness in the worst case. Therefore at least one comparison is necessary.
Edge case: If N = 1 there is no element that is not the largest; the statement assumes N ≥ 2.
A video solution is available for this question — log in and enroll to watch it.