There are n stacks of n identicallooking coins All of the co

There are n stacks of n identical-looking coins. All of the coins in some of these stacks are genuine except for one which is 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.

1. Devise a brute-force algorithm to identify the stacks with the fake coins and determine its worst-case efficiency class.

2. What is the minimum number of weighings needed to identify the stack with the fake coins?

Solution

1) Brute Force Algorithm: Iterate through all the stacks one by one(1 to n) and measure weight of one coin from each. The coin which weights 11gm, that stack is counterfeit.

Algorithm:

for i = 1 to n:

if( weight of a coin(top of stack) of stack(i) == 11gm) print(stack(i) is counterfeit)

Complexity of Brute Force algorithm: O(n) In worst case the last stack we check might be counterfeit, hence our loop can run max of n times.

2) There is only one weighing needed to identify the stack with the fake coin.

Number the coin stacks from 1 to n. Take 1 coin from the first stack, 2 coins from the second, and so on, until all n coins are taken from the last stack.

Weigh all these coins together. The difference between this weight and (n*(n+1)/2)*10,    the weight of (1 + 2 + ... + n) = (n*(n+1)/2) genuine coins, indicates the number of the fake coins weighted, which is equal to the number of the stack with the fake coins.

For example, if the selected coins weigh ((n*(n+1)/2)*10 + 3 ) grams, 3 coins are fake and hence it is the third stack that contains the fake coins.