# Given a set of n balls with different weights and a scale that compares two balls

Write an algorithm to determine if there's a set of > n/4 balls of the same weight. The algorithm cannot exceed O(n log n) time.

One way I was thinking about this was using divide and conquer. My original algorithm was as follows:

findSet(S) #S is the set of n balls
If |S| = 1, return the lone ball
If |S| = 2 or 3, return any ball
Divide S up into 4 subsets of equal length, run findSet on each
If no run returns a ball, return nothing
If a single test returns a ball, weigh the ball against all other balls
in S. If we generate a set of balls > n/4, return the ball

If >=2 tests return balls, let B denote the set of these balls.
For each ball b in B, weight b against all elements in B.
If we generate a set of balls > n/4, return the corresponding b.


I think the algorithm is O(n) because the recurrence would be T(n) = 4T(n/4) + n which can be reduced to O(n log4 n). However, I'm pretty sure this algorithm is incorrect. Primarily, I'm not sure if the base cases will ensure we choose a ball b that is > n/4 in the original set.