<p>You are given an integer <code>n</code> and an array of <strong>unique</strong> integers <code>blacklist</code>. Design an algorithm to pick a random integer in the range <code>[0, n - 1]</code> that is <strong>not</strong> in <code>blacklist</code>. Any integer that is in the mentioned range and not in <code>blacklist</code> should be <strong>equally likely</strong> to be returned.</p>

<p>Optimize your algorithm such that it minimizes the number of calls to the <strong>built-in</strong> random function of your language.</p>

<p>Implement the <code>Solution</code> class:</p>

<ul>
	<li><code>Solution(int n, int[] blacklist)</code> Initializes the object with the integer <code>n</code> and the blacklisted integers <code>blacklist</code>.</li>
	<li><code>int pick()</code> Returns a random integer in the range <code>[0, n - 1]</code> and not in <code>blacklist</code>.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input</strong>
[&quot;Solution&quot;, &quot;pick&quot;, &quot;pick&quot;, &quot;pick&quot;, &quot;pick&quot;, &quot;pick&quot;, &quot;pick&quot;, &quot;pick&quot;]
[[7, [2, 3, 5]], [], [], [], [], [], [], []]
<strong>Output</strong>
[null, 0, 4, 1, 6, 1, 0, 4]

<strong>Explanation</strong>
Solution solution = new Solution(7, [2, 3, 5]);
solution.pick(); // return 0, any integer from [0,1,4,6] should be ok. Note that for every call of pick,
                 // 0, 1, 4, and 6 must be equally likely to be returned (i.e., with probability 1/4).
solution.pick(); // return 4
solution.pick(); // return 1
solution.pick(); // return 6
solution.pick(); // return 1
solution.pick(); // return 0
solution.pick(); // return 4
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>9</sup></code></li>
	<li><code>0 &lt;= blacklist.length &lt;= min(10<sup>5</sup>, n - 1)</code></li>
	<li><code>0 &lt;= blacklist[i] &lt; n</code></li>
	<li>All the values of <code>blacklist</code> are <strong>unique</strong>.</li>
	<li>At most <code>2 * 10<sup>4</sup></code> calls will be made to <code>pick</code>.</li>
</ul>

class Solution:

    # use cumSum
    # sort the blacklist
    # then generate intervals that divide the entire range of ints
    # such that they exclude blacklist
    # i.e. blacklist=[10,25], n = 30
    # arr = [[0,9],[11,24],[26,30]]
    # cumSum = [10, 24, 29]
    # for each range, we pick with prob=size_of_range
    # after picking range, we randomly pick an item from that range
    # prob(num) = range_size/ all_size * 1 / range_size
    # to pick a range, we generate a value k
    # then we can see which range k falls in by using cumSum


    def __init__(self, n: int, blacklist: List[int]):
        self.arr = []
        self.cumSum = []

        if len(blacklist) == 0:
            self.arr = [[0, n-1]]
            self.cumSum = [n]
        else:
            blacklist = sorted(blacklist) 
            # iterate through blacklist
            for i in range(len(blacklist)):
                start = blacklist[i-1]+1 if i> 0 else 0
                end = blacklist[i] - 1

                if end >= start:
                    self.arr.append([start, end])
                    if len(self.cumSum) > 0:
                        self.cumSum.append(self.cumSum[-1]+end-start+1)
                    else:
                        self.cumSum.append(end-start+1)  

            # need to add the range from last blacklist val to end
            start = blacklist[-1]+1
            end = n-1

            if end >= start:
                self.arr.append([start, end])
                if len(self.cumSum) > 0:
                    self.cumSum.append(self.cumSum[-1]+end-start+1)
                else:
                    self.cumSum.append(end-start+1)  
        print(self.arr, self.cumSum)
  

    def pick(self) -> int:
        
        # pick k
        k = random.randint(1, self.cumSum[-1])
        # see which range k falls into by bin searching cumSum
        cumSum_pos = self.bin_search(k)
        # randomly pick an item from the range
        return random.randint(self.arr[cumSum_pos][0], self.arr[cumSum_pos][1])
    
    def bin_search(self, k):
        l, r = 0, len(self.cumSum)-1
        while l <= r:
            mid = (l+r)//2
            if self.cumSum[mid] == k:
                return mid
            elif self.cumSum[mid] > k:
                r = mid - 1
            else:
                l = mid + 1
        return l


class Solution:

    # remapping
    # instead of choosing from 0-n
    # we choose from 0 to n-len(b)
    # we iterate through all blacklisted number in 0 to n-len(b)
    # and remap them to non-blacklisted number

    def __init__(self, n: int, blacklist: List[int]):

        blacklist = sorted(blacklist)
        self.b = set(blacklist)
        self.m = {}
        self.length = n - len(blacklist)
        j = 0
        # iterate through the outside range
        # assign a blacklist number to number outside range
        # i.e. if blacklisted number chosen, we instead choose
        # the out of range number instead
        for i in range(self.length, n):
            if i not in self.b:
                self.m[blacklist[j]] = i
                j += 1

    def pick(self) -> int:
        i = random.randint(0, self.length-1)
        # if i is not blacklisted, return i
        # if i is blacklisted, return the mapping
        return self.m[i] if i in self.m else i

    
class Solution:

    # remapping
    # instead of choosing from 0-n
    # we choose from 0 to n-len(b)
    # we iterate through all blacklisted number in 0 to n-len(b)
    # and remap them to non-blacklisted number

    def __init__(self, n: int, blacklist: List[int]):
        blacklist = sorted(blacklist)
        self.b = set(blacklist)
        self.m = {}
        self.length = n - len(blacklist)
        j = 0
        for i in range(self.length, n):
            if i not in self.b:
                self.m[blacklist[j]] = i
                j += 1


    def pick(self) -> int:
        i = random.randint(0, self.length-1)
        return self.m[i] if i in self.m else i


# Your Solution object will be instantiated and called as such:
# obj = Solution(n, blacklist)
# param_1 = obj.pick()
30200