Simple 10 lines of C++ code with O(B logB) constructor and O(log B) pick() with comments & intuition
Since the goal is to minimize the total calls to rand function, we think about solving for pick using a single call to rand. How can we do that while excluding 
Since the goal is to minimize the total calls to `rand` function, we think about solving for `pick` using a single call to `rand`. How can we do that while excluding the elements in the blacklist? The intuition : \n1. sort the numbers\n1. generate a random number R between 0 to (N - blacklist.length)\n1. search for the first number in the list just greater than R\n1. increment R by index of that number\n1. adjust(inc) R further if more of the blacklisted numbers after the index were jumped over after incrementing the value of R\n\nLet\'s trace the idea with an example.\n\n`Example-   N:10   blacklist:[5,9,2] `\n\nLet `B=3` be the length of the blacklist array. \n\nPick function is supposed to generate a random number from our now `valid array: [0,1,3,4,6,7,8]`\n\nWhat we want to do is use `rand` to generate an `index` to pick a number from our valid array rather than value. Which can be done as  `r = rand() % (N-B)` which in our example is `r = rand() % 7`.\n\nSuppose we get `r = 4`. We can now simply return the fourth element in the valid array which is `4`. But the problem is that we do not have the valid array. We can not create such an array since we dont have the storage space to store `N <= 1000000000` numbers in worst case.\n\nWhat we can do is use the inclusion exclusion principle to extrapolate what value we would have had in the **valid array** from our knowledge of **excluded numbers** which here is the blacklist array.\n\nSo in the example we generated `r = 4`. We now simply find the number of elements in the blacklist array that are smaller than `r` and add that value to `r` to say that these elements would have been skipped in the **valid array**. This search can be optimized by using binary search to find the first greater element in a sorted list. In C++ we have a function `upper_bound(v.begin(), v.end(), ele)` which returns the iterator to the first element greater than the `ele` in a sorted `vector v`. \n\nIn our example, `upper_bound` will return the iterator to `firstGreaterEle = 5` in the sorted vector `[2, 5, 9]`. We thus skip only the element 2 giving us `skippedIndices=1`. We than adjust for the skipped indices using `r += skippedIndices`, giving us `r=5`.\n\nOur problem does not end here though. We can see in our example that after adding the `skippedIndices`, we may **jump over or reach** more of the blacklisted numbers. We now keep incrementing `r` and `firstGreaterEle`  till we reach an element `*firstGreaterEle<=r`\n\nHere we go! O(B log B) for sorting and O(log B) for binary search (upper_bound) function.\n\n```\nclass Solution {\n    int _N;\n    int reducedN;\n    vector<int> _blacklist;\npublic:\n    Solution(int N, vector<int> blacklist) {\n        // 1 sort the numbers\n        // 2 generate a random number R between 0 to (N-B.length)\n        // 3 Search for the first number in the list just greater than R\n        // 4 increment R by index of that number\n        // 5 adjust(inc) R further if more of the blacklisted numbers after the index were jumped over after incrementing the value of R\n        \n        _blacklist = blacklist;\n        sort(_blacklist.begin(), _blacklist.end());\n        _N = N;\n        reducedN = N - _blacklist.size();\n    }\n    \n    int pick() {\n        int r = rand() % reducedN;\n        auto firstGreaterEle = upper_bound(_blacklist.begin(), _blacklist.end(), r);\n        int skippedIndices = firstGreaterEle - _blacklist.begin();\n        r = r + skippedIndices;\n        while(firstGreaterEle<_blacklist.end() && *firstGreaterEle<=r) {\n            r++;\n            firstGreaterEle++;\n        }\n        \n        return r;\n    }\n};\n\n ```
[]