The problem resolves around find which of the coin is uneven in weight of all other coins. Suppose there are around 8 coin out of them one is heavy/light then others and we have one scale where we can compare two things

This is an interesting another problem which I had found while dicussing with Vatsal a friend of mine, which was asked in his interview for some company.

Suppose out of eight we know that one of them is of higher weight then others. The simplest way to achieve the solution for this problem would be doing a binary search like approach where you would divide in two equal half check which side is higher then again divde in two equal half and then look for higher side where you can reach finally to a conclusion on which coin is higher

Same approach can be taken when one of coin is lighter then others. For eight coin it would take atleast 3 round for above solution.

1
2
3
4
5
6
7

88889888
   /\
8888 9888
      /\
    98 88
    /\
    9 8

1
2
3
4
5
6
7

88887888
   /\
8888 7888
      /\
    78 88
    /\
    7 8

Now to optimize the solution we can look into another approach. Here as in above we are sure that one of the coin is higher in weight then others. In this case we can do something like this. We can take two coin aside and equally divide rest 6 coins. Then we can compare three with other three. If weight of one of side is higher then we can discard all other coin then this three as we are aware that only one coin is of higher weight then other. Now we have three coins left. We can weight two of them, if one of side is higher then we have found then coin. If both are equal then the one which we didnt weigh is coin with higher weight.

Other secenario could be where when we had compare 3 - 3 coins on each side they would have been of equal weigh. In that case we can weigh left two coins and get which one is higher.

1
2
3
4
5

898888 88
  /\
898 888
/\
8 9 8  

1
2
3
4
5

889888 88
  /\
889 888
/\
8 8 9  

1
2
3
4
5

888888 98
  /\
888 888 98
        /\
        9 8

In above solution we have optimized it further such that instead of three operation we are doing just two opertation.

The intresting problem here would be when we would not be aware whether a coin is lighter or heavier. In that case how we can optimize it. Whose solution we can try to find may in another blog post.