Monday, February 3, 2014

Find heavy ball

Problem:
9 identical balls. one ball is heavy. find the heavy ball with only 2 measurements ........ dead easy.

Solution:
this is super easy. split the ball into three groups with 3 balls each. pick two groups out to measure if they are equal weight. this way, you could find out which group contains the heavy ball. Then from this particular group, you could pick two to do one more measurement, this way, you find out the heavy ball

Complexity:
time - O(1)
space - O(1)
Links and credits:
http://www.careercup.com/question?id=5204967652589568

No comments:

Post a Comment