A correct and accepted solution with explanation and proof
We can split \[0, N) into several accept intervals based on blacklist. For example, we can split 9, \[2,3,5,7] into \[1,1], \[4,4], \[8,9]. Then we random choos
We can split \\[0, N) into several accept intervals based on blacklist. For example, we can split 9, \\[2,3,5,7] into \\[1,1], \\[4,4], \\[8,9]. Then we random choose a white interval with the  probability of $len_i/total_len$\uFF0Cand uniformly random choose a num in the interval.\n\nWith Law of Total Probability we can know that\nP(white_num) = P(interval_i)\\*1/len_i = len_i/total_len * (1/len_i) = 1/total_len.\nSo it is a uniform distribution, and the time complexity is O(\\log len(blacklist))\n\n```\nclass Solution:\n    def __init__(self, N, blacklist):\n        """\n        :type N: int\n        :type blacklist: List[int]\n        """\n        \n        if not blacklist:\n            self.interval = [[0, N-1]]\n            self.prob = [N]\n            return \n        \n        # transform all the consecutive black nums to black intervals\n        blacklist.sort()\n        blacklist.append(float(\'inf\')) # to handle the last black interval\n        last = blacklist[0]\n        black_interval = []\n        tmp = [blacklist[0]]\n        for i in blacklist[1:]:\n            if i == last + 1:\n                last = i\n            else:\n                tmp.append(last)\n                black_interval.append(tmp)\n                tmp = [i]\n                last = i\n                \n        # gen white intervals\n        interval = []\n        if black_interval[0][0] == 0:\n            tmp = [black_interval[0][1] + 1]\n            if len(black_interval) == 1:\n                interval.append([black_interval[0][1] + 1, N-1])\n            black_interval.pop(0)\n        else:\n            tmp = [0]\n        for s, e in black_interval:\n            tmp.append(s-1)\n            interval.append(tmp)\n            tmp = [e+1]\n        if black_interval and black_interval[-1][-1] != N-1:\n            interval.append([black_interval[-1][-1]+1, N-1])\n        self.interval = interval\n        \n        # calc prefix sums\n        self.prob = [self.interval[0][1] - self.interval[0][0] + 1]\n        for s, e in self.interval[1:]:\n            self.prob.append(self.prob[-1] + e - s + 1)\n        \n    def pick(self):\n        # random pick a white interval basing the len of each intervals\n        P = random.randint(1, self.prob[-1])\n        idx = bisect.bisect_left(self.prob, P)  \n        return random.randint(*self.interval[idx])\n```
[]