Odd ball out

Question: You are given 9 balls. 8 of them weigh the same while 1 is heavier than the others. How can you determine which ball is the odd one out using just two comparisons?

Related Tags:

Simplify to 3 balls, 1 comparison

Let's simplify this problem using just 3 balls. If we were given 2 balls that weighed the same and one that were heavier, how would we solve this using just 1 comparison?

We can easily do this by picking any two random balls and weighing them against each other.

  1. Select any two balls.
  2. If the two balls weigh the same, the third will be the heavier one.
  3. If one of the two balls is heavier, then that ball is the heavier one.

Now 9 balls, 2 comparisons

Simple enough, right? Now with nine balls, we can do a similar.

  1. Group balls into three's.
  2. Grab any two sets of balls and weigh them against each other.
  3. If they weigh the same, then the heavier ball is in the set you didn't weigh.
  4. If they weight different, then the heavier ball is in the heavier set.
  5. Now with the three balls in the heavier set, simply use the algorithm above, and you'll find the odd ball out.

Get it? 27 balls and 3 comparison should be a cinch now. ;-)

Came up with a better solution or have a question? Comment below!

Next Challenge: Reverse a String