Dec 19, 2008

You have 10 balls out of which 8 have the same weight while two are heavy. How many comparisons you would need to find the heavier ones in the worst c

You have 10 balls out of which 8 have the same weight while two are heavy. How many comparisons you would need to find the heavier ones in the worst case.

I think that is 4 times,
Apart 10 balls into 3 sets like set1 bbb, set2 bbb, set3 bbbb
Weight set1 and set2, if not equal, we can get heavier ball in next 2 weights
If equal, the two heavier balls can be either in set3 or one in set1 and the other in set2.
Take 3 balls from set3 and weight with set1, if set1 heavier, the heavier ball should be in set1 and set2, otherwise the heavier balls should be in set3. so we can get the heavier ball in next two weights

No comments:

Post a Comment