Cracking Coding Interview - 6.1 the Heavy Pill

The Heavy Pill: You have 20 bottles of pills. 19 bottles have 1.0 gram pills, but one has pills of weight 1.1 grams. Given a scale that provides an exact measurement, how would you find the heavy bottle? You can only use the scale once.

Hints: #186, #252, #319, #387

备注：scale的意思是磅秤

解法

1.1 比 1.0 大 0.1，所以要利用这个多出来的0.1来识别是哪个瓶子。我们给瓶子编号从1-20，然后从瓶子中拿出和编号数量一样的药片，那么总重量 = 1 + 2 + 3 + ... + j * 1.1 + ... + 18 + 19 + 20。其中 1 <= j <= 20，j就是第几个药瓶。

我们知道如果所有药片都是1克，那么总重量 = 1 + 2 + 3 + ... + 18 + 19 + 20 = 210，两者相减得到的就是多出来的 j * 0.1 克。那么只需将结果除以0.1就能得到j，即第几个药瓶。