Java solution with HashSet 100% fast - logic explained
Idea : If count of banned elements is greater than or equal to N/3, then simply create a list of allowed elements, and return a random item from allowed list.\n
**Idea :** If count of banned elements is greater than or equal to N/3, then simply create a list of allowed elements, and return a random item from allowed list.\nIf count of banned elements is less than N/3, then this makes p = 2/3 probability that any randomly selected element will NOT be in the banned list.\n\n**Expected** number of trials for first success when sucess probability is p = 1/p\n\nSo, **expected** number of calls to Random = 3/2 (practically 2).\n\n```\nclass Solution {\n    HashSet<Integer> banned;\n    List<Integer> allowed;\n    Random r;\n    int N;\n    \n    public Solution(int N, int[] blacklist) {\n        this.N = N;\n        banned = new HashSet<Integer>();\n        allowed = new ArrayList<Integer>();\n        \n        for(int x : blacklist){\n            banned.add(x);\n        }\n        \n        int M = banned.size();\n        if(M >= (N/3)){\n            for(int i = 0; i < N; i++){\n                if(!banned.contains(i)){\n                    allowed.add(i);\n                }\n            }\n        }\n        \n        r = new Random();\n    }\n    \n    public int pick() {\n        if(allowed.size() > 0){\n            // too many blacklisted elements\n            int index = r.nextInt(allowed.size());\n            return allowed.get(index);\n        }else{\n            while(true){\n                int index = r.nextInt(N);\n                if(!banned.contains(index))\n                    return index;\n            }\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\n```
[]