C solution using binary search
IntuitionThe "proper" solution to this problem is to use a hash map that maps blacklisted numbers to whitelisted numbers. This takesO(n)time to set up theSoluti
# Intuition
The "proper" solution to this problem is to use a hash map that maps blacklisted numbers to whitelisted numbers. This takes $$O(n)$$ time to set up the `Solution` and $$O(1)$$ time to pick a random number (although hash maps have a fair bit of overhead behind the scenes).

This approach uses a simpler binary search algorithm to set up the `Solution`and pick the random numbers. Set up time is $$O(n \log n)$$ for sorting the blacklisted numbers. Depending on how many blacklisted numbers there are, it will either take $$O(\log n)$$ time to pick a random number, or an additional $$O(n)$$ time to set up the `Solution` and $$O(1)$$ time to pick a number.
# Approach
The simplest approach is to sort the `blacklist` then repeatedly generate a random number in the range `[0..n-1]` untile a binary search fails to find the number in the `blacklist`. As long as `blacklist` is relatively small, this works fine but if there are too many numbers in the `blacklist` then it will require too many calls to the random number generator which will result in TLE.

The numbers `[0..n-1]` can be divided into two lists: a `blacklist` (given) and a `whitelist` (all the numbers not in `blacklist`) of sizes `blacklistSize` and `whitelistSize` (`= n - blacklistSize`) respectively. If `blacklistSize < whitelistSize` then the simple approach will take on average of two attempts to find a random number that is not in `blacklist` with an $$O(\log $$ blacklistSize$$)$$ time for each attempt. This is acceptable.

Otherwise, we can generate a `whitelist` by iterating through the numbers `[0..n-1]` and if the number is not in `blacklist` then add it to the `whitelist`. It will take $$O(n)$$ time to set up the `whitelist`. Thereafter to pick a number, generate a random index in the range `[0..whitelistSize-1]` and return the number in the `whitelist` that corresponds with this index (a `O(1)` operation).

Note that we can't use the second method if `whitelistSize >> blacklistSize` since setting up the array could result in MLE.
# Complexity
- Time complexity:$$O(n \log n)$$ to set up and $$O(\log n)$$ for each pick.
- Space complexity: $$O(n)$$
# Code
```c []
typedef struct {
    int n;
    bool useBlacklist;
    int *list;
    int listSize;
} Solution;

bool binSearch(int *a, int n, int x);
void quickSort(int *a, int lo, int hi);

Solution* solutionCreate(int n, int* blacklist, int blacklistSize) {
    Solution *obj = (Solution*) malloc(sizeof(Solution));
    obj->n = n;
    quickSort(blacklist, 0, blacklistSize - 1);
    int whitelistSize = n - blacklistSize;
    srand(time(NULL));
    if (blacklistSize < whitelistSize) {
        obj->list = blacklist;
        obj->listSize = blacklistSize;
        obj->useBlacklist = true;
        return obj;
    }
    int *whitelist = (int*) malloc(whitelistSize * sizeof(int));
    int k = 0, j = -1;
    for (int i = 0; i < blacklistSize; ++i) {
        while (++j < blacklist[i]) whitelist[k++] = j;
    }
    while (++j < n) whitelist[k++] = j;
    obj->useBlacklist = false;
    obj->list = whitelist;
    obj->listSize = whitelistSize;
    return obj;
}

int solutionPick(Solution* obj) {
    if (obj->useBlacklist) {
        int num;
        do {
            num = rand() % obj->n;
        } while (binSearch(obj->list, obj->listSize, num));
        return num;
    }
    return obj->list[rand() % obj->listSize];
}

void solutionFree(Solution* obj) {
    if (!obj->useBlacklist) free(obj->list);
    free(obj);
}


/**
 * Your Solution struct will be instantiated and called as such:
 * Solution* obj = solutionCreate(n, blacklist, blacklistSize);
 * int param_1 = solutionPick(obj);
 
 * solutionFree(obj);
*/

bool binSearch(int *a, int n, int x) {
    int lo = 0, hi = n-1;
    while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        if (a[mid] == x) return true;
        if (a[mid] < x) lo = mid + 1;
        else hi = mid - 1;
    }
    return false;
}

void insertionSort(int *a, int lo, int hi) {
    int i, j, t;
    for (i = lo+1; i <= hi; ++i) {
        t = a[i];
        j = i-1;
        while (j >= lo && a[j] > t) {
           a[j+1] = a[j];
           --j;
        }
        a[++j] = t;
    }
}

void quickSort(int *a, int lo, int hi) {
    int pv, pi, i, j, t;
    if (lo >= hi - 10) {
        insertionSort(a, lo, hi);
        return;
    }
    pi = (lo + hi) / 2;
    pv = a[pi];
    a[pi] = a[hi];
    a[hi] = pv;
    i = lo - 1;
    j = hi;
    do {
        do { i++; } while (a[i] < pv);
        do { j--; } while (a[j] > pv && j > lo);
        if (i < j) {
            t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    } while (i < j);
    a[hi] = a[i];
    a[i] = pv;
    quickSort(a, lo, i-1); 
    quickSort(a, i+1, hi);
}
```
['C']