CareerCup

I don't think there is any way to find an odd ball with less than 4 tries (for the worst case). I will tell it to the interviewer that in case of 8 balls, we can get it in 3 tries. Which comes to the order of log(n). (cos 2^3 = 8). If you are telling me that there is a way more efficient than log(n) (cos log(9) > 3), then I would love to know that. :-)

1. divide the balls into 3 ball groups viz A,B,C
2. now weigh A & B. If A=B [in weight] then C is our group. Else,
2a. A & C are to be weighed. the one having unusual weight is picked. This would also tell if one group is heavier or lighter. Suppose C was the group we sought [for the sake of simplicity, we assume whichever is the odd man out is named C].
3. now, if 2 was the case: then weigh two balls from C, if they are equal, then third is our ball. else
3a. measure 3 balls, taking 2 at a time. this will mean 1 more weighing.
4. If 2a was the case, repeat 3 and 3a. but since we know whether the ball is heavy or light, we would not have the confusion. so if one ball is heavy (say) we come to know this is the one, because we had already judged that in 2a.

No. of steps = 3 .

For 9 balls,
Divide them into 3 groups A, B and C of 3 balls each

1) Compare A and B
2) Compare B and C

if A != B and B = C , A contains the ball
if A != B and B!= C , B contains the ball
if A = B and B!= C , C contains the ball

Now we know the set containing the odd ball and are down to just 3 balls

Let the set contain three balls x,y,z .

[ When we used the balance for detecting the odd set, we came to know whether the odd ball is lighter or heavier ]

3) Compare x and y
if x = y , z is the odd ball
if x!= y , depending upon our observation [ lighter or heavier , we find out the odd ball between x and y ]

So , this variation does not have a best or worst case as we have to carry out steps 1 and 2 to determine whether the odd one is lighter or heavier. So in any case , we will require 3 steps

Also, the 8 ball problem requires 2 steps if the odd one is known to be lighter/heavier . Suppose it is heavier

Divide it into a set of 3 balls A = 1,2,3 B = 4,5,6 and C = 7,8

1) Compare A and B . If A = B then goto step 2 . Else goto step 3
2) Compare 7 and 8 and the heavier is the odd one
3) From the heavier set between A and B , compare any 2 balls. If they are equal , third one is odd . Else the one which is heavier is odd.

Thus, 2 steps

1. Group 9 balls into sets of 3,3 and 3
2. Compare group1 and group2, if both are equal, go to step 4(proceed with group3)
3. Else, Comapare group1 with group3, if they are equal proceed with group2, else with group1
4. Divide balls into 1, 1 and 1
5. Compare ball1 with ball2 once, then with ball3 once.
6. We know the lightest of heaviest ball by now!

After reading question again - it seems that we have identify if 9th ball is heavy or lighter that others.
It is possible in 2 weings only.
1. Divide balls in 3 groups A = 4, B =4, C =1
2. Compare A and B if same go to step 3. else go to step 4.
3. Compare any ball from A or B with ball in C. if ball in C is heavy then 9th ball is heavy else lighter. stop.
4. Choose the group which is heavy lets say A is heavy, divide A in to two groups A1=2 and A2=2.
5. if A1 == A2 means all balls is group A are even. and ball in group B is of less weight. else 9th ball is heavy as A was heavier than B. stop

Further, if we have to really identify defective ball we have divide 9 balls into A=3, B=3 and C=3 and this method is already explained above.

It can be done in 2 steps
Divide the number of balls into set of 3 - A, B, and C
1) Compare A and B, if A > B move than heavier ball is in set A, else if B > A, than heavier ball is in set B else in set C.
2) Divide the set with heavier ball into 1, 1, 1 each.
3) Repeat step 1 to find heavier ball.

Number of weight reqd = 2.