The ith time you see a candidate, you will have a probability of to select it. (i start from 1) So the overall probability of choosing the xth candidate is , where m is the total number of candidates. (1 <= x <= m) It is because if we finally decide to choose xth candidate is independent from whether we changed our decision during any encounter with a candidate before the xth. And at the encounter of the xth candidate, we choose to change which is of probability . Then we did not change during any encounter with the rest of the candidates. So we need to multiply p by which would finaly result in .
from random import randint class Solution(object): def __init__(self, nums): """ :type nums: List[int] :type numsSize: int """ self.nums = nums def pick(self, target): """ :type target: int :rtype: int """ ret = -1 count = 0 for i, x in enumerate(self.nums): if x == target: if randint(0, count) == 0: ret = i count += 1 return ret # Your Solution object will be instantiated and called as such: # obj = Solution(nums) # param_1 = obj.pick(target)