Generate a random integer from 0 to N-1 which is not in the list

Question

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) ?

Answer 1

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.

1. 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.

2. Conduct binary search on array K[].

   • Initial i = K.length/2 = 1.

3. 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.

4. 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.

5. 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.

6. 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.

Answer 2

Binary search.

The basic algorithm:

(not quite the same as the other answer - the number is only generated at the end)

• Start in the middle of K.

• By looking at the current value and it's index, we can determine the number of pickable numbers (numbers not in K) to the left.

  Similarly, by including N, we can determine the number of pickable numbers to the right.

• Now randomly go either left or right, weighted based on the count of pickable numbers on each side.

• Repeat in the chosen subarray until the subarray is empty.

• Then generate a random number in the range consisting of the numbers before and after the subarray in the array.

The running time would be O(log |K|), and, since |K| < N-1, O(log N).

The exact mathematics for number counts and weights can be derived from the example below.

Extension with K containing a bigger range:

Now let's say (for enrichment purposes) K can also contain values N or larger.

Then, instead of starting with the entire K, we start with a subarray up to position min(N, |K|), and start in the middle of that.

It's easy to see that the N-th position in K (if one exists) will be >= N, so this chosen range includes any possible number we can generate.

From here, we need to do a binary search for N (which would give us a point where all values to the left are < N, even if N could not be found) (the above algorithm doesn't deal with K containing values greater than N).

Then we just run the algorithm as above with the subarray ending at the last value < N.

The running time would be O(log N), or, more specifically, O(log min(N, |K|)).

Example:

N = 10
K = {0, 1, 4, 5, 8}

So we start in the middle - 4.

Given that we're at index 2, we know there are 2 elements to the left, and the value is 4, so there are 4 - 2 = 2 pickable values to the left.

Similarly, there are 10 - (4+1) - 2 = 3 pickable values to the right.

So now we go left with probability 2/(2+3) and right with probability 3/(2+3).

Let's say we went right, and our next middle value is 5.

We are at the first position in this subarray, and the previous value is 4, so we have 5 - (4+1) = 0 pickable values to the left.

And there are 10 - (5+1) - 1 = 3 pickable values to the right.

We can't go left (0 probability). If we go right, our next middle value would be 8.

There would be 2 pickable values to the left, and 1 to the right.

If we go left, we'd have an empty subarray.

So then we'd generate a number between 5 and 8, which would be 6 or 7 with equal probability.

Answer 3

This can be solved by basically solving this:

Find the rth smallest number not in the given array, K, subject to conditions in the question.

For that consider the implicit array D, defined by

D[i] = K[i] - i for 0 <= i < L, where L is length of K

We also set D[-1] = 0 and D[L] = N

We also define K[-1] = 0.

Note, we don't actually need to construct D. Also note that D is sorted (and all elements non-negative), as the numbers in K[] are unique and increasing.

Now we make the following claim:

CLAIM: To find the rth smallest number not in K[], we need to find right most occurrence of r' in D (which occurs at position defined by j), where r' is the largest number in D, which is < r. Such an r' exists, because D[-1] = 0. Once we find such an r' (and j), the number we are looking for is r-r' + K[j].

Proof: Basically the definition of r' and j tells us that there are exactlyr' numbers missing from 0 to K[j], and more than r numbers missing from 0 to K[j+1]. Thus all the numbers from K[j]+1 to K[j+1]-1 are missing (and these missing are at least r-r' in number), and the number we seek is among them, given by K[j] + r-r'.

Algorithm:

In order to find (r',j) all we need to do is a (modified) binary search for r in D, where we keep moving to the left even if we find r in the array.

This is an O(log K) algorithm.