CareerCup

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