Intuitive approach - Choosing between 2 easy approaches on runtime
Intuition\n Describe your first thoughts on how to solve this problem. \nThere can be 2 approaches to solve this.\nApproach 1\nGenerate random integers until a 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThere can be 2 approaches to solve this.\nApproach 1\nGenerate random integers until a whitelisted number is generated.\nApproach 2\nMaintain a list of whitelisted numnbers and pick one randomly from it.\n\nApproach 1 will not work if most numbers are blacklisted\nApproach 2 will not work if most numbers are whitelisted (MLE)\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nDecide between Approach 1 and Approach 2 dynamically based on number of whitelisted and blacklisted numbers\n\n# Complexity\n- Time complexity: O(m) to iniitialise\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n- Space complexity: O(m) to maintain list of whitelisted / blacklisted\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n- Number of calls to rand() : O(1)\n\n# Code\n```\n/*\nApproach 1\ngenerate random integer in range (0, n - 1), generate again if blacklisted\nE = 1 + m / n * E\nE (n - m) / n = 1\nE = n / (n - m)\n\nif m is < n/2 this approach works as E = 2, which means we only call generate twice\n\nTime O(1) per pick\nMemory O(M) for maintainng blackisted hash table\n\nApproach 2\n\nMaintain a list of non-blacklisted numbers and pick each of them randomly.\n\nTime O(1) per pick\nMemory O(N - M) for maintaining list of whitelisted numbers\n\nThis solution does not work when N is large\n\n*/\n\nclass Solution {\npublic:\n\n    int approach;\n\n    int n, m;\n\n    unordered_set<int> hash_set;\n\n    vector<int> whitelist;\n\n\n    Solution(int nn, vector<int>& blacklist) {\n        n = nn;\n        m = blacklist.size();\n        for(auto it : blacklist) {\n            hash_set.insert(it);\n        }\n        if(m * 2 < n) {\n            approach = 1;\n        }\n        else {\n            approach = 2;\n            for(int i = 0; i < n; i++) {\n                if(hash_set.find(i) == hash_set.end()) {\n                    whitelist.push_back(i);\n                }\n            }\n        }\n    }\n    \n    int pick() {\n        if(approach == 1) {\n            while(true) {\n                int val = rand() % n;\n                if(hash_set.find(val) == hash_set.end()) {\n                    return val;\n                }\n            }\n        }\n        else {\n            int idx = rand() % whitelist.size();\n            return whitelist[idx];\n        }\n    }\n};\n\n/**\n * Your Solution object will be instantiated and called as such:\n * Solution* obj = new Solution(n, blacklist);\n * int param_1 = obj->pick();\n */\n```
['C++']