There are n stacks of n identical looking coins All of the c

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?

Solution

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.