Qm
BrainteasersJane StreetCitadel

The median of five numbers in six comparisons

algorithmscomparisonsselectionsorting

You have five distinct numbers, a, b, c, d and e, hidden in sealed envelopes. The only operation allowed is to compare two of them and learn which is larger.

Find the median (the third largest) using at most six comparisons. Sorting all five would take seven; show how to save one, and explain why five comparisons can never be enough.

Show a hint

Compare a with b and c with d. Then compare the two smaller ones. The smaller of those is below three numbers and cannot be the median. Now the median is the second smallest of the four survivors.

Your answer

Solving needs a free account

Answers, streaks and solutions unlock when you are signed in. Reading the question and the hint stays free.

Create a free accountSign in

Discussion

Sign in to join the discussion · reading is open to everyone

💡 Discussion rules

  1. No full solutions here. Hints and approaches only.
  2. Complexity, edge cases and intuition are the point.
  3. Interview experiences are welcome. Respect your NDAs.

Loading discussion…

Learn the concepts

The theory behind this question.

Finding the Median With Few ComparisonsQuickselect and Top-K SelectionWhy the Naive Shuffle Is BiasedThe Bisection MethodDetecting Cycles in an Iterated Sequence

Related questions

Sort four items in five comparisonsThe heaviest and the runner-up among eight coinsBoth the lightest and the heaviest of ten coinsFinding one honest agent among liarsFind the duplicated number
All questions →