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.

# Alternative Solution

**sajib_only**#1

**cykel**#2

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.

**sajib_only**#3

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.

**ravi_stoic**#5

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.