Finding both the minimum and the maximum — Aptitude Question
Finding both the minimum and the maximum: What is the minimum number of comparisons needed to find both the… Answer and worked solution on CodeKairo.
- Topic: Data Structures & Algorithms
- Section: Programming MCQs
- Difficulty: Hard
- Time target: 150 seconds
Question
What is the minimum number of comparisons needed to find both the smallest and the largest of 100 distinct integers?
Options
- 99
- 148
- 150
- 198
Show the answer and the worked solution
Correct answer: B. 148
Worked solution
- First compare the elements in pairs: 100 elements give 50 comparisons.
- The winner of each pair joins a set of 50 candidates for the maximum; the loser joins a set of 50 candidates for the minimum.
- Finding the maximum among 50 candidates takes 49 comparisons, and the minimum among the other 50 takes 49 more.
- The total is 50 + 49 + 49 = 148, which is the general bound ⌈3n/2⌉ − 2.
Answer: 148.
The idea
Scanning naively costs about 2n comparisons. Pairing first halves the number of candidates each element can belong to, and 3n/2 − 2 is provably optimal.
Shortcut. Each of the 99 non-maxima must lose once and each of the 99 non-minima must win once, 198 verdicts; only the 50 opening pairings of untouched elements deliver two verdicts at once, so 198 − 50 = 148.
Common trap. 198 runs two separate scans of 99 comparisons each, never letting one comparison serve both the minimum and the maximum.
All Data Structures & Algorithms questions · placement mock tests