0

The question is as follows (the classic nine balls question):

"You have nine balls. One of them is heavier, and you are given a balance to find out which one is heavier. You are allowed to use this balance twice and it tells you which side is heavier."

I was given an explanation, but I cannot make sense of it. This is extracted from page 95 of Cracking the Coding Interview. I will add more details if needed included the answer provided in the book. I am currently preparing for a coding interview as you may have guessed.

SDG
  • 245
  • 2
    Let's start with a smaller case: Can you solve the 3 ball, one balance case? – Element118 Oct 27 '15 at 23:05
  • I really want to see the answer given in the book, since Element118 already gave the answer in a way, which can't - quite sure of it - be much more simplified. What makes you worry? – user190080 Oct 27 '15 at 23:14

1 Answers1

1

The key here is that you know that one of the balls is heavier.

So, if you have 3 balls, then you can figure out which is heavier with one weighing. If two balance, then the other is the heavier, otherwise the side which goes down has the heavier ball.

So, the question is, how to reduce the problem to one set of three balls.

Split them into three groups of 3.

Weigh two groups. If they balance, you know the other group contains the heavier ball, otherwise you know the heavier group.

You are now left with one group of three balls, so one more weighing will tell you the heavier ball.

copper.hat
  • 172,524