Given n coins, some of which are heavier, find the number of heavy coins?
Given n coins, some of which are heavier, algorithm for finding the number of heavy coins using O(log^2 n) weighings. Note that all heavy coins have the same weight and all the light ones share the same weight too.
You are given a balance using which you can compare the weights of two disjoint subsets of coins. Note that the balance only indicates which subset is heavier, or whether they have equal weights, and not the absolute weights.
I won't give away the whole answer, but I'll help you break it down.
O(log(n)) algorithm to find a single heavy coin. O(log(n)) algorithm to split a set into two sets with equal number of heavy and light counts plus up to two leftovers (for when there are not even amounts of each). Hints:
O(log(n)) hints at binary search O(log^2(n)) with two O(log(n)) algorithms? 上一篇: 找到两个不同的硬币