An algorithm for identifying two unequal heavier / lighter coins out of n given coins

摘要

Counterfeit coin problem has been considered for a very long time and is a topic of great significance in Mathematics as well as in Computer Science. In this problem, out of n given coins, two or more false coins (the coins are classified as false because their weights are different when compared to a standard coin) are present which have the same appearance as the other coins. This problem belongs to the class of combinatorial group testing problem which finds several applications in hidden graph construction problem etc. In this paper, we have constructed an optimal algorithm to determine two false coins out of a given number of coins. In addition, our objective is to solve the problem in minimum number of comparisons with the help of an equal arm balance. Our proposed algorithm is able to find out the fake coins using O(log n) comparisons.