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.


1 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

  • $\begingroup$ Would it be possible to presort in n log n time? Perhaps using a mergesort like algorithm with the scale to sort balls? $\endgroup$ Commented Mar 10, 2018 at 3:12
  • $\begingroup$ You can but then the overall runtime becomes O(N log N). Ahh I see what you mean. Your required runtime is that. However I believe the O(N) solution is correct which might help other users in the future. $\endgroup$
    – sunnytheit
    Commented Mar 10, 2018 at 3:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.