Java | 39ms | beats 99% | randomly pick up numbers from all or only from allowed
Intuition\nFirst of all, let\'s forget about random calls minimization requirement, this problem can be interesting even without this requirement.\n\nAssume tha
# Intuition\nFirst of all, let\'s forget about random calls minimization requirement, this problem can be interesting even without this requirement.\n\nAssume that we need to pick up random integer $x$ such that $0 \\leq x < n$ and we have $k$ blocked integers. So, we have $n - k$ allowed integers.\nWe have 2 cases:\n1. if $n - k < k$ then we can find all allowed integers and then just randomly pick up them\n2. if $n - k >= k$ then number of allowed integers can be too large (e.g when $n = 1e9$). But when we\'ll randomly pick up integers from range $[0, n)$ then probability to pick up blocked number will be equal to $k/n \\leq 1/2$. So, we can randomly pick up numbers, and ***on average*** it will require only constant number of random calls ($\\mathrm{avg} \\leq 2$, see proof below)\n\n# Approach\nOne can easiliy implement solution using algorithm description from the Intuition section.\n\nBut we need to prove that case 2 will have average pick time $O(1)$.\nLet\'s assume that $q$ is blocked numbers fraction ($q = k/n \n\\leq 1/2$)\nWhat will be probability of the event: we called random generator $i$ times in single `pick` in order to generate allowed number?\nIt will be $p(i) = q^{i-1} (1-q)$ (we randomly selected blocked numbers for the first $i-1$ attempts, and on $i$-th attempt we picked up allowed number). Let\'s calculate expected time for `pick` procedure:\n$$\n\\mathsf{E} [\\mathrm{pick \\; time }]\n    = \\sum\\limits_{i = 1}^{\\infty} i \\; p(i)\n    = \\sum\\limits_{i = 1}^{\\infty} i \\; q^{i-1} (1 - q)\n    = \\frac{1}{(1-q)^2} (1 - q)\n    = \\frac{1}{1-q}\n    \n$$\n$$\n\\;\\;\\;\\;\\;\\; \\left| \\; \n\\sum\\limits_{i = 1}^{\\infty} i \\; q^{i-1}\n    = \\frac{\\partial}{\\partial q}\\left( \n            \\sum\\limits_{i = 0}^{\\infty} q^{i} \\right)\n    = \\frac{\\partial}{\\partial q}\\left( \\frac{1}{1-q} \\right)\n    = \\frac{1}{(1-q)^2}\n\\right.\n$$\nSo, on average we will use $\\frac{1}{1-q}$ random calls in case 2, and because $q \\leq 1/2$ in this case we\'ll use on average no more than $2$ random calls.\n\n# Complexity\n- Time complexity: init - $O(k)$, pick - $O(1)$\n\n- Space complexity: $O(k)$\n\n# Code\n```\nclass Solution {\n    private final Random random = new Random();\n\n    private final boolean useBlocked;\n\n    private final int n;\n    private final Set<Integer> blocked;\n\n    private final List<Integer> allowed;\n\n    public Solution(int n, int[] blacklist) {\n        this.n = n;\n        int blSize = blacklist.length;\n        useBlocked = (blSize * 2 <= n);\n        blocked = new HashSet<>(blSize);\n        allowed = new ArrayList<>();\n        for (int val : blacklist) {\n            blocked.add(val);\n        }\n        if (!useBlocked) {\n            for (int val = 0; val < n; ++val) {\n                if (!blocked.contains(val)) {\n                    allowed.add(val);\n                }\n            }\n        }\n    }\n    \n    public int pick() {\n        if (useBlocked) {\n            int val = random.nextInt(0, n);\n            while (blocked.contains(val)) {\n                val = random.nextInt(0, n);\n            }\n            return val;\n        } else {\n            int idx = random.nextInt(0, allowed.size());\n            return allowed.get(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 \n```
['Randomized', 'Java']