Monday, May 10, 2010

Find the Odd ball

You are given 80 balls and out of which only 1 has more weight than other 79. also, you are given weighing machine which can weigh any number of balls of 2 sets( 40 40 or 25 25 etc) at one time

Assume the ball we need to find is X. Divide into 3 groups, A (27 balls), B (27 balls), C (26 balls)

Step 1: Weight A vs B, whichever is heavier has X. If equal, then C has X. If C has X, choose a random ball in A and put into C so that C has 27 balls.

Step 2: After step 1, we determine which group has X, and the group size is 27. Divide into 3 smaller groups, each of size 9, and repeat the same procedure.

In short, we have, 80 -> 27 -> 9 -> 3 -> 1, 4 steps in total to find X.

In general , if there are n balls , log_3(n) is the answer, or find out how many powers 3 should be raised to cross the total number of balls

No comments:

Post a Comment