Problem: Divide and Conquer
A scientist left her cloning machine on. While she was away, a gang of frogs managed to get inside her office and use the cloning machine. The scientist returned surprised to have her office full of frogs, but excited to test a new hypothesis. The scientist suspects that one or more frogs may have taken advantage of the cloning machine to gain a selective genetic advantage.
We say that two frogs are identical if we genetically sequence the frogs and their DNA is 99.99% identical. The mad scientist has a machine that will determine whether or not two frogs are genetically identical, but it is costly to operate so she wants to minimize its use.
The only operation you are allowed to perform is to take two frogs and determine if they are genetically identical. Develop an O(n log n) algorithm that, given n frogs, determines if there is a set of more than n/2 frogs that are genetically identical.