You have a pile of N coins and there is one coin in the pile that is either
lighter or heavier than the rest. You have a scale that is expensive with
time use, so you want to be conservative with your weighing. Write a
recursive algorithm and find the time complexity.
Here is my answer:
1. Split the pile of n coins into 4 different piles
2. Weigh each pile and eliminate the 3 piles which are the same weight, but
keep a single coin from an eliminated pile for comparison (Call it "c"
3. Repeat this process recursively for the remaining pile
4. When down to the last 2 coins, whichever coin is a different weight than
coin "c" is the odd coin in the pile.
T(N) = T(N/4) + c
O(logN)
Is this correct?