[Python] use either Whitelist or Blacklist, simple
The idea is simple, if there are too many blacklisted numbers (more than a third of all possible numbers), then just make a whitelist and randomly choose from i
The idea is simple, if there are too many blacklisted numbers (more than a third of all possible numbers), then just make a whitelist and randomly choose from it.\n\nElse we know that only 1/3 of possible random choices are blacklisted, so we can just do a few random draws and the probability of continously choosing blacklisted numbers decreases exponentially, e.g. for 12 draws  `(1/3) ** 12` it is less than 2 in a million.\n\n```\nimport random\n\nclass Solution:\n    def __init__(self, n: int, blacklist: List[int]):\n        self.n = n\n        if len(blacklist) > n//3:\n            self.whitelist = list(set(range(0, n)) - set(blacklist))\n        else:\n            self.blacklist = set(blacklist)\n\n    def pick(self) -> int:\n        if hasattr(self, \'whitelist\'):\n            return random.choice(self.whitelist)\n        while (rand:= random.randint(0, self.n - 1)) in self.blacklist:\n            continue\n        return rand\n```
['Python']