Question: You are give 12 identical looking balls. One of them is fake (could be heavier or lighter) than the rest of the 11 (all the others weight exactly the same). You a provided with a simple mechanical balance and you are restricted to only 3 uses. Find the fake ball.
Answer: For convenience sake, let’s name the balls 112. This question is quite tricky. If you want to warm up your skills, you can try this easier 8 ball problem first.
Ok, let’s get on with it.
First we weigh {1,2,3,4} on the left and {5,6,7,8} on the right. There are three scenarios which can arise from this.
If they balance, then we know 9, 10, 11 or 12 is fake. Weigh {8, 9} and {10, 11} (Note: 8 is surely not fake)
If they balance, we know 12 is the fake one. Just weigh it with any other ball and figure out if it is lighter or heavier.
If {8, 9} is heavier, then either 9 is heavy or 10 is light or 11 is light. Weigh {10} and {11}. If they balance, 9 is fake (heavier). If they don’t balance then whichever one is lighter is fake (lighter).
If {8, 9} is lighter, then either 9 is light or 10 is heavy or 11 is heavy. Weigh {10} and {11}. If they balance, 9 is fake (lighter). If they don’t balance then whichever one is heavier is fake (heavier).
Phwww, that was confusing enough but we are not done yet.
If {1,2,3,4} is heavier, we know either one of {1,2,3,4} heavier or one of {5,6,7,8} is lighter but it is guarantees that {9,10,11,12} are not fake. This is where it gets really tricky, watch carefully. Weigh {1,2,5} and {3,6,9} (Note: 9 is surely not fake).
If they balance, then either 4 is heavy or 7 is light or 8 is light. Following the last step from the previous case, we weigh {7} and {8}. If they balance, 4 is fake(heavier). If they don’t balance then whichever one is lighter is fake (lighter).
If {1,2,5} is heavier, then either 1 is heavy or 2 is heavy or 6 is light. Weigh {1} and {2}. If they balance, 6 is fake (lighter). If they don’t balance then whichever one is heavier is fake (heavier).
If {3,6,9} is heavier, then either 3 is heavy or 5 is light. Weigh {5} and {9}. They won’t balance. If {5} is lighter, 5 is fake (lighter). If they balance, 3 is fake (heavier).
If {5,6,7,8} is heavier, it is the same situation as if {1,2,3,4} was heavier. Just perform the same steps using 5,6,7 and 8. Unless maybe you are too lazy to try and reprocess the steps, then you continue reading the solution. Weigh {5,6,1} and {7,2,9} (Note: 9 is surely not fake).
If they balance, then either 8 is heavy or 3 is light or 4 is light. Following the last step from the previous case, we weigh {3} and {4}. If they balance, 8 is fake(heavier). If they don’t balance then whichever one is lighter is fake (lighter).
If {5,6,1} is heavier, then either 5 is heavy or 6 is heavy or 2 is light. Weigh {5} and {6}. If they balance, 2 is fake (lighter). If they don’t balance then whichever one is heavier is fake (heavier).
If {7,2,9} is heavier, then either 7 is heavy or 1 is light. Weigh {1} and {9}. If they balance, 7 is fake (heavier). If they don’t balance then 1 is fake (lighter).
Voila!!!!
Head is spinning yet. Take out a paper and try it out just to get things clear. Now that you know how to solve this problem, you are ready to take on this world.
If you have any questions, please feel free to send me an email at support@mytechinterviews.com. If you have any interview questions which you feel would benefit others, I would love to hear about it.
If you're looking for some serious preparation for your interviews, I'd recommend this book written by a lead Google interviewer. It has 189 programming questions and solutions:
GooD work
In your first step part B, if 19 is lighter, you cant say fake ball is in 19 because you don’t know if the fake ball is lighter or heavier. Not knowing if the ball is heavier or light is what makes this question tougher.
For the 12 Identical Balls Problem,
using the same method, the maximum number of balls can be up to 27.
First step: 19 weight with 1018,
A. balance ==> fake ball in 1927.
B. 19 lighter ==> fake ball in 19.
C. 19 heavier ==> fake ball in 1018.
Second step: take the group of nine balls (A is 1927, B is 19, C is 1018)
weight the first six balls with three on each side.
a. balance –> fake ball in the leftover 3.
b. imbalance –> fake ball in the lighter group of 3.
Third step: take any two of the three and weight one on each side.
I) balance –> the leftover one is the fake ball.
II) imbalance –> the lighter one is the fake.
New

Reply
Reply all
Forward

Delete
Mark as ▼
Move to ▼

Print
[Refresh]
{9,10} compare with {11,12}. if both are equal then the problem reduces to 8 ball problem which can be done in 2balances.
How about dividing {1,2,3,4,5} ,{6,7,8,9,10},{11,12}
if ur lucky u get in 2 uses else 3
lets split them into 4 grps of 3 each..A(1,2,3) B(4,5,6) C(7,8,9) D(10,11,12)…then weigh A against B and C vs D..So now in 2 tries we can find out which grp has the ball with the diffe weight..then in another 1 try we can find out the different ball…correct me if am wrong guys….
Ahaaa… You are absolutely right about that. I corrected the solution now. 🙂
Thanks
Under :If {1,2,3,4} is heavier,
If {3,6,9} is heavier, then either 3 is heavy or 5 is light or 6 is light. Weigh {5} and {6}. If they balance, 3 is fake (heavier). If they don’t balance then whichever one is lighter is fake (lighter).
Only possibilities are Either 3 is heavier or 5 is lighter. 6 can’t be lighter as {3,6,9} is heavier.
I’m sorry, but there is a slight inconsistency in the subcase where {1,2,3,4} is heavier, and then after weighing {1,2,5} with {3,6,9} the latter turns out to be heavier. The answer states that in that case, either “3 is heavy or 5 is light or 6 is light”. The first two possibilities are correct, but 6 cannot possibly be light, since {3,6,9} would not be heavier then. Therefore, it can only be that either 3 is heavy or 5 is light, which simplifies this subcase a little bit. One should then take any ball other than 3 and weigh it against 5 — if they balance out, then 3 is fake (heavier), and if not then 5 is fake (lighter).
Similarly, in the very last subcase where {5,6,7,8} is heavier and then {7,2,9} is heavier, it is impossible for 2 to be light, as is currently mentioned in the answer. Either 7 is heavy or 1 is light.
Hi Sbudah, your solution will work if we knew that the fake ball was heavier but we don’t. The fake ball could be heavier or lighter. We do not know that.
What about weighing {1,2,3,4,5,6} against {7,8,9,10,11,12}. If either is heavier we take the lighter side off the scales and bring in 3 from the heavier side e.g. 16 was lighter so we remove it and replace it with {7,8,9} and weigh them against {10,11,12}.
Again, the heavier side remains. We remove two balls from the heavier side and place only one of them on the other side of the scale e.g. 10 against 11. If they balance, then it is the one that was not on the scale — in this case it’s 12. If one is heavier then it is the fake ball.