Alternative Solution


There is also another solution based on Randomization.
If the array has at least one number which is at least N/3 times there, then if we choose a number randomly, there is 1/3 chance of choosing it. So, if we randomly choose a number 20/30 times, there is a high chance of choosing it, we can check if it occurs more than N/3 times with a loop. This will run in C*o(N) where C is 20-30.


That’s an interesting approach, thanks for sharing. Of course, one would also need a way of detecting whether no element occurs > n / 3 times.


Yes. If we cannot find a number which occurs more than n/3 times with 20/30 trials, then we can say that the probability of an existing solution is almost zero.


True, it’s a neat solution.


well if i toss a coin 10 times and heads comes out 8 out of 10 times that doesn’t mean probability of head to tail is 8/10. Similarly for this case what if every time the randomly selecting number is same. how can we guarantee that we select 20 out of 30 numbers ?


First of all your solution is wrong since this probabilistic method does not ensures a right solution.
Second the complexity comes out to be worse than O(nlogn) for the given input range.


Can you post implemented one!!!