## Algorithm

Problem Name: 710. Random Pick with Blacklist

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

Optimize your algorithm such that it minimizes the number of calls to the built-in random function of your language.

Implement the `Solution` class:

• `Solution(int n, int[] blacklist)` Initializes the object with the integer `n` and the blacklisted integers `blacklist`.
• `int pick()` Returns a random integer in the range `[0, n - 1]` and not in `blacklist`.

Example 1:

```Input
["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"]
[[7, [2, 3, 5]], [], [], [], [], [], [], []]
Output
[null, 0, 4, 1, 6, 1, 0, 4]

Explanation
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
```

Constraints:

• `1 <= n <= 109`
• `0 <= blacklist.length <= min(105, n - 1)`
• `0 <= blacklist[i] < n`
• All the values of `blacklist` are unique.
• At most `2 * 104` calls will be made to `pick`.

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const Solution = function (N, blacklist) {
this.map = new Map()
for (let b of blacklist) this.map.set(b, -1)
this.M = N - this.map.size
for (let b of blacklist) {
if (b < this.M) {
while (this.map.has(N - 1)) N--
this.map.set(b, N - 1)
N--
}
}
}

Solution.prototype.pick = function () {
const p = Math.floor(Math.random() * this.M)
if (this.map.has(p)) return this.map.get(p)
return p
}
``````
Copy The Code &

Input

cmd
["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"] [[7, [2, 3, 5]], [], [], [], [], [], [], []]

Output

cmd
[null, 0, 4, 1, 6, 1, 0, 4]

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:

def __init__(self, N, blacklist):
self.forbidden, self.n, self.used, self.cur = set(blacklist), N, set(), 0
def pick(self):
while self.cur in self.forbidden: self.cur += 1
if self.cur < self.n: num, self.cur = self.cur, self.cur + 1
else: num = self.used.pop()
return num
``````
Copy The Code &

Input

cmd
["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"] [[7, [2, 3, 5]], [], [], [], [], [], [], []]

Output

cmd
[null, 0, 4, 1, 6, 1, 0, 4]