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)Links and credits:
space - O(1)
http://www.careercup.com/question?id=5204967652589568
No comments:
Post a Comment