Generate a random integer from 0 to N-1 which is not in the list
algorithm
Solution
You can use the fact that all the numbers in K[] are between 0 and N-1 and they are distinct.
For your example case, you generate a random number from 0 to 3. Say you get a random number `r`. Now you conduct binary search on the array K[].
`Initialize i = K.length/2`.
Find `K[i] - i`. This will give you the number of numbers missing from the array in the range 0 to i.
For example K[2] = 5. So 3 elements are missing from K[0] to K[2] (2,3,4)
Hence you can decide whether you have to conduct the remaining search in the first part of array K or the next part. This is because you know `r`.
This search will give you a complexity of `log(K.length)`
EDIT: For example,
N = 7
K = {0, 1, 4} // modified the array to clarify the algorithm steps.
the function should return any random number { 2, 3, 5, 6 } with equal probability.
Random number generated between `0` and `N-K.length` = `random{0-3}`. Say we get `3`. Hence we require the 4th missing number in array K.
Conduct binary search on array `K[]`.
- `Initial i = K.length/2 = 1`.
Now we see `K[1] - 1 = 0`. Hence no number is missing upto `i = 1`. Hence we search on the latter part of the array.
Now `i = 2. K[2] - 2 = 4 - 2 = 2`. Hence there are `2` missing numbers up to index `i = 2`. But we need the 4th missing element. So we again have to search in the latter part of the array.
Now we reach an empty array. What should we do now? If we reach an empty array between say `K[j] & K[j+1]` then it simply means that all elements between `K[j]` and `K[j+1]` are missing from the array `K`.
Hence all elements above `K[2]` are missing from the array, namely `5` and `6`. We need the `4th element` out of which we have already discarded `2 elements`. Hence we will choose the second element which is `6`.
Problem
You are given `N` and an `int K[]`. The task at hand is to generate a equal probabilistic random number between `0 to N-1` which doesn't exist in K. `N` is strictly a integer `>= 0`. And `K.length` is < N-1. And `0 <= K[i] <= N-1`. Also assume K is sorted and each element of K is unique. You are given a function `uniformRand(int M)` which generates uniform random number in the range `0 to M-1` And assume this functions's complexity is O(1). Example: N = 7 K = {0, 1, 5} the function should return any random number { 2, 3, 4, 6 } with equal probability. I could get a O(N) solution for this : First generate a random number between 0 to N - K.length. And map the thus generated random number to a number not in K. The second step will take the complexity to O(N). Can it be done better in may be O(log N) ?