Odd Coin Weighing Algorithm Consider the following scenario and then develop an

Question

Odd Coin Weighing Algorithm

Consider the following scenario and then develop an algorithm to solve it. Suppose you have 9 coins and one of them is heavier than others. Other 8 coins weight equally. You are also given a balance. Develop an algorithm to determine the heavy coin using only two measurements using the balance. Now, suppose you have n coins and one of them is heavier. You can assume that n is a power of 3. Generalize the algorithm you have developed above for this case. What is the running time of your algorithm?

I understand how to solve the problem mathematically, but I can't seem to figure out how to write the algorithms in pseudo code.

Explanation / Answer

Start by grouping coins into 3 grups of equal size, compare weight of first and second group if both are of equal weight then the odd coin is in third group, otherwise the group having more weight is having odd coin. Now iteratively search in the group which contains odd coin(i.e. by divding into three groups). When the group size is 3, then find the odd coin in one measurement. The algorithm is as follows:
Let A be the set of all n coins.

Measurement(A,n):

1. if(n==3)

2. compare first and second if not equal output heavy coin other output third coin

3. size=n/3

4. group1=A[1,...n/3] group2=A[n/3+1,...2n/3] group3=A[2n/3+1,...n]

5. if(weihght(group1)>group(group2)) Measurement(A[1,..n/3],size)

6. else if(weihght(group1)<group(group2)) Measurement(A[n/3+1,2n/3],size)

7. else Measurement(A[2n/3,...,n],size)

Above algorithm runs in O(log3n) steps.

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

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