Suppose that among n identical$-$looking coins, one is fake, where n $>=3.$ Moreover, it is unknown whether the fake coin is lighter or heavier than the genuine one. With a balance scale, you can compare any two sets of coins. That is$,$ by tipping to the left, to the right, or staying even, the balance scale will tell you whether the two sets weight the same, or which of the two sets is heavier than the other but not by how much. Please use the prune and search strategy to design an efficient algorithm for detecting the fake coin. Please also analyze the number of weighting needed by your algorithm in worst case.