# Python solution using Monte Carlo & Accepted

• So Monte Carlo here basically works as follows: you randomly guess a number in the list and check if it does appears more than ⌊ n/2 ⌋ times. You set an epsilon which means you have a probability of epsilon to make a wrong answer.

``````import math
import random
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
epsilon = 0.000000000000000000000001
k = int(math.ceil(math.log(1.0/epsilon) / math.log(2.0)))# How many times you want to guess

ll = list(set(nums))

for i in range(1,k+1):
j = random.randint(0, len(ll)-1)
x = ll[j]
if x == 0:
for k in range(0, len(ll)):
j = (j+1) % len(ll)
if ll[j] != 0: break
x = ll[j] * 1
ll[j] = 0
if nums.count(x) > int(len(nums)/2): return x
return 0
``````

-Update-

A better version, Thanks to @StefanPochmann. I even once ACed with epsilon=0.1!

``````import math
import random
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
epsilon = 0.01
k = int(math.ceil(math.log(1.0/epsilon) / math.log(2.0)))
for i in range(1,k+1):
j = random.randint(0, len(nums)-1)
x = nums[j]
if nums.count(x) > int(len(nums)/2): return x
return 0
``````

• Seems like a bad idea to me to reduce it to a set. That reduces the probability of picking the majority element from over 50% to the same probability as every other element.

• @StefanPochmann Thanks for correction, I didn't think of that.

• I noticed that U used
`if nums.count(x) > int(len(nums)/2): return x`
I do not understand why u guess, just traverse `ll` and get the answer.

• @quheng Well I didn't put much effort on optimizing my code, just wanted to try this algorithm out. After all it isn't the best algorithm for this problem.

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