Consider the following problem. Someone gives you a bag with n very valuable ant
ID: 3691536 • Letter: C
Question
Consider the following problem. Someone gives you a bag with n very valuable antique coins and a balancing scale. A balancing scale allows you to determine the weight of an object by placing the same weight on both sides of the scale (or balance). You're told that one of the n coins is a fake coin. If can find the fake coin you get to keep the entire bag of coins! You're given the additional information that all the coins are exactly the same weight, except for the fake coin, which is lighter than the others. There is one catch. You can use the scale at most lg n times. (After that it will disintegrate.) Give a divide and conquer algorithm that will find the fake coin using the balancing scale at most lg n times. You may describe the algorithm or give pseudocode. In either case, clearly indicate how the algorithm works. Do NOT assume that the number of coins is a power of two.Explanation / Answer
Let n be total no:of coins
if n is even :
divide the coins into 2 equal parts (same no:of coins on all parts)
as the fake coin is lighter than others, take the lighter part of above divided parts
neglect the other part and do divide odd/even fuction as per the no:of coins in part
At last if only 2 coins remains, then the lighter of the 2 coins will be the fake coin
if n is odd :
divide the n coins into 3 part like a=(n-1)/2, b=(n-1)/2 , c=1, so that a+b+c=n
if weight of a == weight of b then:
c is the fake coin
else if weight of a < weight of b
fake coin will be in a(beacuse it is lighter)
if a is even, do the steps for even as mentioned before with part a
else do steps for a add with part a
else if weight of a > weight of b
fake coin will be in b(beacuse it is lighter)
if a is even, do the steps for even as mentioned before with part b
else do steps for a add with part b