O(1) allowed and forbidden partition
We calculate the count of allowed numbers; and create a "logical partition".Upper partition numbers  are excluded from being picked directly. Some might be vali

We calculate the count of allowed numbers; and create a "logical partition".
Upper partition numbers  are excluded from being picked directly. Some might be valid or invalid.

Invalid numbers from the lower partition are mapped 1:1 to valid numbers from the upper partition.
The rest of the upper partition is composed of any invalid numbers that already belonged there.

Pick is O(1) time complexity [hash table lookup]

# Code
```cpp []
class Solution {

    unordered_map<int, int> disallowed_to_allowed;
    int n_;

public:
    Solution(int n, vector<int>& forbidden) : n_(n - forbidden.size()) {

        unordered_set<int> disallowed_all(cbegin(forbidden), cend(forbidden));
        disallowed_to_allowed.reserve(forbidden.size());
        int last_allowed = n - 1;
        for (int val : forbidden) {
            // Already in upper partition.
            if (val >= this->n_) {
                continue;
            }
            // Find next valid number in upper partition.
            for (; disallowed_all.contains(last_allowed); --last_allowed)
                ;
            disallowed_to_allowed[val] = last_allowed;
            --last_allowed;
        }
    }

    int pick() {
        const int random_num = rand() % (n_);
        if (auto it = disallowed_to_allowed.find(random_num);
            it != disallowed_to_allowed.end()) {
            return it->second;
        } else {
            return random_num;
        }
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(n, blacklist);
 * int param_1 = obj->pick();
 */
```
['C++']