A stack of fake coins There are n stacks of n identical-looking coins. All of th

Question

A stack of fake coins There are n stacks of n identical-looking coins. All of the coins 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 efciency class.

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

Explanation / Answer

1) Worst Approach

Go and check each stack , If the total weight is 100 then stack is fine otherwise its faulty.

In Worst case we might have to do N weighing of N stack i.e O(N2) coins are processed and
O(N) times stack are processed i.e Total N stack in worst case.


Best Approach

We will number the stack as 1 to 10 .

Then we will take 1 coin from first stack, 2 from second, three from third .....and 10 from the last one.


Weigh all these together . . ..

So genuine coins will be 1+2+3+4...10 = 55 genuine coins
Weight = 55*10 = 550 grams and 55 genuine coins.


( Total wight we got )- 550 = x

x will determine our fake stack.

For EXAMPLE we get the discrepancy like for example if we get 553 , then 3 coins are fake that means 3rd stack is the culprit.



2) Best Approach : We wighted it once only., minimum number of weighings needed to identify the stack with the fake coins is ONE
Worst Approach : We might have to weight N-1 times

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.