Given a set of n balls with different weights and a scale that compares two balls
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.


Do Worst-Case Linear-Time Selection to find the median of the entire array.
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.
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