Divide and Conquer You have a rare gold coin. You dropped it into a pile of fake gold coins that look identical. You want to find your real coin and all you know is that it weighs more than the fake coins. You have a scale that you can use to compare the weights of two coins (or two sets of coins). It will tell you which of the two is heavier 1. or if they are equal in weight a) Design a brute force algorithm to solve this problem and state how many times your algorithm uses the scale if you have n coins (including the real one
b) Describe a Divide and Conquer algorithm for this problem