# Java random number solution

1. Randomly pick a number between 0 and n-1, loop over the array to see if this number appears more than n / 3 times. - O (n)
2. repeat 1 for 100 times.

Therefore the time complexity is O(100n), which is essentially still O(n).

Suppose we have 2/3 chance to miss a desired number in one pick, the possibility of missing this number in 100 picks would be (2/3)^100, which is 10E-18. This possibility is so low, maybe even lower than the possibility of leetcode server crash in the next second.

So I guess this solution is sufficiently reliable. If not, we could repeat step 1 for 1000 times, to make sure finding out the two numbers.

Moreover, this solution could be generated to solve questions like "find all elements that appear more than n/m times."

``````   public class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> output = new ArrayList<>();
for (int i = 0; i < 100; i += 1) {
int count = 0;
int index = (int)(nums.length * Math.random());
for (int j = 0; j < nums.length; j += 1)
if (nums[index] == nums[j])
count += 1;
if (count > nums.length / 3 && !output.contains(nums[index]))
}
return output;
}
}``````

• Very creative idea!! But frankly speaking, the methods we write in Leetcode are basic/fundamental level methods, which could be called billions of time when the software is running. For example, during a 3D game is running, the math function Math.sqrt may be used almost millions of time every minute, one wrong answer could lead to disastrous result. So although your solution passed OJ, I am afraid it's stil flawed.

• That's true. This solution is never going to be absolutely correct. Plus, it takes longer than O(n^2) time for n < 100.

However, maybe I should emphasize the 2e-18 error possibility. That is, if this method is called a million times per second, wrong answer occurs every 10,000 years!

Maybe it is still not enough. How about increase number of times in step 2 to 150? Wrong answer occurs every 8,000,000,000,000 years - 500 times the age of universe...

• Make sense!! Everything is a balance of cost and reliability including algorithms. When reliability is good enough, we need to try best to lower cost. I now think a 2e-18 possibility is good enough.

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.