An answer to this question on Stack Overflow.

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

If you are running this many times, it probably pays to speed up your generation operation: O(log N) time just isn't acceptable.

Make an empty array G. Starting at zero, count upwards while progressing through the values of K. If a value isn't in K add it to G. If it is in K don't add it and progress your K pointer. (This relies on K being sorted.)

Now you have an array G which has only acceptable numbers.

Use your random number generator to choose a value from G.

This requires O(N) preparatory work and each generation happens in O(1) time. After N look-ups the amortized time of all operations is O(1).

A Python mock-up:

import random
class PRNG:
	def __init__(self, K,N):
		self.G = []
		kptr   = 0
		for i in range(N):
			if kptr<len(K) and K[kptr]==i:
				kptr+=1
			else:
				self.G.append(i)
	def getRand(self):
		rn = random.randint(0,len(self.G)-1)
		return self.G[rn]
prng=PRNG( [0,1,5], 7)
for i in range(20):
	print prng.getRand()