Qm
Brainteasers

Sort four items in five comparisons

algorithmssortingcomparisonsinformation

Four stones have four different weights. Your only tool is a balance that compares two stones at a time.

  1. Arrange the four stones in order of weight using at most five weighings.
  2. Show that four weighings can never be enough.
Show a hint

For part 2, count the possible orderings and the possible outcome sequences. For part 1, compare two pairs, compare the two winners, then find where the remaining stones fit.

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 ComparisonsBalance-Scale Weighing ProblemsWhy the Naive Shuffle Is BiasedThe Bisection MethodOptimal Card Guessing When You Count What Is Gone

Related questions

The median of five numbers in six comparisonsThe heaviest and the runner-up among eight coinsBoth the lightest and the heaviest of ten coinsFind the heavy ball among 27 in three weighingsEight batteries, four good, one flashlight
All questions →