Given $n$ coins, some of which are heavier, come up with an 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 have the same weight too.

What I need is how to give an equal split to coins which the to part have same weight, in $O(log(n))$.


First I assume we can weight a lot of coins at the same time. (otherwise, the problem become redundant)

My algorithm for the problem is not quite like yours as I do not use divide and conquer method.

The algorithm:

  1. find 1 heavy and 1 light coin. [O(log(n) - binary search could work here]

  2. compare the next element with both the heavy and light coin, now we know whether it is light or heavy. thus we know (without loss of generality) of 2 light and 1 heavy coin.

the idea of the algorithm is to now check over the 2 next elements and compare them with the light ones, or the next one and compare it to the heavy. (runtime will remain ok as each will be multiplied each time and it can be multiplied only log times each).

the remaining problem to solve here is what to do if I don't get an equality on any of the above (it is not equal the group of light nor the heavy), in this case, we can use divide and conquer, as we can "play" with the amount of heavy and light coins on the other side until we find our desired ammount. total time will be log(n) iterations of multiplying, each iteration needs an O(log(max_pile)), worst case analysis would say the max pile is always smaller than n thus the worst case run time is O(log^2(n))


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.