Simple Java solution with Binary Search
We need to first sort B. Let L denote its length.\nLet M = N-L. We will generate numbers from the interval [0, M). Possible cases for a random value r are as fo
We need to first sort `B`. Let `L` denote its length.\nLet `M = N-L`. We will generate numbers from the interval `[0, M)`. Possible cases for a random value `r` are as follows;\n* If it is in `[0,B[0])`, we can return `r` as it is.\n* If it is in `[B[0], B[1]-1)`, we can return `r+1`.\n* If it is in `[B[1]-1, B[2]-2)`, we can return `r+2`.\n* ...\n* If it is in `[B[i]-i, B[i+1]-(i+1))`, we can return `r+i+1`. Note that `B[i] < r+i+1 < B[i+1]`, so it is safe.\n* ...\n* If it is in `[B[L-1]-(L-1), M)`, we can return `r+L`. Note that `B[L-1] < r+L < N`, so it is safe.\n\nSo we will make a binary search on the interval boundaries (i.e. `B[i]-(i+1)`) and apply an offset according the the interval that the random number falls into.\n\n```\nclass Solution {\n\n    int[] b;\n    int M;\n    \n    public Solution(int N, int[] blacklist) {\n        b = blacklist;\n        this.M = N - b.length;\n        \n        Arrays.sort(b);\n        for (int i = 0; i < b.length; i++) {\n            b[i] -= (i+1);\n        }\n    }\n    \n    public int pick() {\n        int r = (int) Math.floor(Math.random()*M);\n        int index = Arrays.binarySearch(b, r);\n        if (index < 0) {\n            return r - (index+1);\n        } else {\n            // here is a bit tricky. we need to select the first boundary that \n            // matches, because the intervals degenerate if B[i+1]=B[i]+1.\n            while (index > 0 && b[index-1] == r)\n                index--;\n            return r + index;\n        }\n    }\n}\n```
[]