| hard | strategy |
You are given N coins which look identical (assume N = 2^k). But actually some of them are pure gold coins (hence are heavy) and the rest are aluminum coins with thin gold plating (light). You are given one beam balance with two pans. What is the number of weighing required to separate the gold from fake coins? (all gold coins have equal weights & all fake coins too have the same weight)
Divide and conquer
It takes about (log N)^2 operations: Divide the set of 2^k with d heavy coins into two sets, each with 2^(k-1) coins with floor(d/2) heavy coins. If we can do this, we can determine the number of heavy coins in O(log n)^2 operations.
Dividing the set can be done in O(log n). (*Later)
So, T(n) = T(n/2) + O(log n) T(n) = O(log^2 n). To be exact, this is k*(k+1)/2 . where k = log N
(*Sub-Algorithm) Divide the set into two sets A and B of equal number of coins. Let A greater than B and to make both side of equal weight, I need to shift few coins from A to B and equal number of coins from B to A. So divide A into A1 and A2, and B into B1 and B2. Move A2 from A into B and B1 from B into A now if (A1,B1) is greater than (B2,A2) then I have not moved enough coins from A into B so as to make B part heavy enough hence you divide A1 into A11,A12 and move A12 in B side similarly u move B21 into A side on the other hand if (A1,B1) is less than (A2,B2) I have more than enough coins from A into B hence move B12 back into B and A21 back into A now measure again. Do it so on...
Note that we are doing this in O(log n) as each time the number of coins we are moving is reduced by half. So, In O(log n), we are done.
To prove that solution always exists, we do it by induction: difference in the number of heavy coin after kth iteration cannot be more than 2^(n-1-k) So, after n-1th iteration, it can be more that 1 coin. Hence, done. :)