Problem
You are given a pan balance scale and a bag of n coins. Any quantity of coins may be placed in each of the balance's pans. The scale will tell you if the set of coins in one pan and the set in the other pan have the same weight, or if one set is heavier. There is a coin in the bag that weighs differently than the other coins. Except for this one coin, every other coin weighs the same.
1. Write pseudo-code for a divide-and-conquer algorithm to ?nd the coin that weighs differently than the other coins. You may assume that n is power of 3.
2. Write the recursion formula of your algorithm.
3. What is the running time of your algorithm?