I have a number `n` and a set of numbers `S ∈ [1..n]*` with size `s` (which is substantially smaller than `n`). I want to sample a number `k ∈ [1..n]` with equal probability, but the number is not allowed to be in the set `S`.

I am trying to solve the problem in at worst `O(log n + s)`. I am not sure whether it's possible.

A naive approach is creating an array of numbers from 1 to n excluding all numbers in `S` and then pick one array element. This will run in `O(n)` and is not an option.

Another approach may be just generating random numbers `∈[1..n]` and rejecting them if they are contained in `S`. This has no theoretical bound as any number could be sampled multiple times even if it is in the set. But on average this might be a practical solution if `s` is substantially smaller than `n`.