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

Question

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.

Answer 1

Assume you have a sorted array of all weights. If any such element existed then more than %25 of that array had to be occupied with that element. Then either element at %25 marker, %50 marker and %75 marker has to contain such element. So we have 3 candidates but no such sorted array. Assume N is divisible by 4 below. There might some tweaks to be done for edge cases which can be handled.

1. Do Worst-Case Linear-Time Selection to find the median of the entire array.
2. Create two arrays of size |N / 2| both. For the first one but everything smaller than the median. For the second one put everything that is larger. If either of the arrays or not full pad the array with the median element. Then find the median of both of these arrays as mentioned in step 1.
3. We have 3 candidates. For each candidate count how many of them have equal weight. If any has counter more than |N / 4| output this element.

Runtime: Each step is linear with respect to input. We iterate over the entire balls multiple times but still it is O(N).

Problem with the proposed algorithm is mainly the probable imbalance of the random partitions of the set