Qm
BrainteasersOptiverSIG

Both the lightest and the heaviest of ten coins

weighingcomparisonspairingalgorithms

You have ten coins, all of different weights, and a balance that compares one coin against one coin. You must identify both the heaviest and the lightest coin.

Finding the heaviest takes 9 comparisons. Finding the lightest among the remaining 9 takes 8 more, for a total of 17.

Can you do better? What is the smallest number of comparisons that guarantees you find both?

Show a hint

Compare the coins in pairs first. After one comparison, the heavier coin of the pair can never be the lightest overall, and the lighter one can never be the heaviest. That single comparison has done double duty.

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 ComparisonsWhy the Naive Shuffle Is BiasedThe Bisection MethodDetecting Cycles in an Iterated SequenceDynamic Programming Basics

Related questions

The heaviest and the runner-up among eight coinsFind the heaviest of eight with a balanceThe median of five numbers in six comparisonsSort four items in five comparisons12 coins, one fake of unknown weight
All questions →