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 efficiency class.
b. What is the minimum number of weighings needed to identify the stack
with the fake coins?

Explanation / Answer

Solution:

The brute force method will be to start weighing Every stack and when the weight of the stack is 11n then it means that the stack is a counterfeit.

Algorithm:

So the worst case outcome will occur only when the counterfeit bag is weighted at last.

So that will give us O(n) running time.

b)

Fortunately, we have one more method which is optimal and saves much time

Here we will take 1 coin from stack1, 2 coins from stack2, 3 coins from stack3, and ....n coins from stackn

and weigh it at once

What will happen now is the (Result of the above given formula- (n(n+1)/2)*10) will be the stack number which is counterfeit.

For example:

suppose 10 stacks are there and stack5 is a counterfeit,

then our calculation will be 1*(10)+2*(10)+3*(10)+4*(10)+5*(11)+ 6*(10)+ 7*(10)+8*(10)+ 9*(10)+ 10*(10)= 555

Now as per our formula counterfeit stack number= (1*(10)+2*(10)+3*(10)+4*(10)+5*(11)+ 6*(10)+ 7*(10)+8*(10)+ 9*(10)+ 10*(10))- (10*11)/2= 5.

So the answer is only one weight (minimum number of weighting) is required to find fake coins.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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