**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:

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.

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

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

- Group balls into three's.
- Grab any two sets of balls and weigh them against each other.
- If they weigh the same, then the heavier ball is in the set you didn't weigh.
- If they weight different, then the heavier ball is in the heavier set.
- 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: Check if all chars in a string are unique