There are n stacks of n identical looking coins. All of the coin in one of these
ID: 3922737 • Letter: T
Question
There are n stacks of n identical looking coins. All of the coin in one of these stacks are counterfeit, while all the coins in the other stacks are genuine. Every genuine coin weighs 10 grams; every fake weighs 11 grams. You have an analytical scale that can determine the exact weight of any number of coins.
a. Devise a brute force algorithm to identify the stack with the fake coins and determine its worst-case efficiency class.
b. What is the minimum number of weighing needed to identify the stack with the fake coins?
Explanation / Answer
a. Brute force way to do this would be to take one coin from each of the n stacks and weigh them till we find the counterfeit. Hence the number of times we need to use the scale is n times in the worst case scenario.
Algorithm:
for i in range(0, n):
int w = weight coin i[0]
if w==11:
return i
b) However, there is a much better way to do this and the algorithm would take just 1 time to do the weighing and find the fake coins.
Take 1 coin from 1st stack, then 2 coins from second stack, 3 from third and so on.
On weighing these coins together, we'll know the fake stack by taking the offset from 10*n*(n+1)/2.
Algorithm:
for i in range(0, n):
take coins from stack i coins [0 to i]
add to a new stack of coins that needs to be weighed.
weigh the new stack of coins which contains 1 coin from 1st stack, 2 coins from 2nd stack and so on till n coins from the nth stack.
the fake stack = total weight of the new stack - 10*n*(n+1)/2
since, 10*n*(n+1)/2 would be the ideal weight if all the coins were of weight 10 grams.
Hence, with this algorithm we'll need the weighing scale just once.