Pick A Random Number Not In A List

I have a list: > S = [1,8,93,3,8] I need to pick a random number that is not in the list but within the max range of value. I am more concerned about time complexity O(n). The

Solution 1:

If the list consists of integers and any number is acceptable:

S = [1,8,93,3,8]
number = 0.5

If the number must be an integer:

S = [1,8,93,3,8]
number = max(S) + 1

If the number must be an arbitrary integer between the largest and smallest elements in the list:

S = [1,8,93,3,8]
number = next(iter(set(range(min(S)+1, max(S))) - set(S)))

If the number must be a psuedorandom integer between the largest and smallest elements in the list:

import random
S = [1,8,93,3,8]
number = random.choice(list(set(range(min(S)+1, max(S)))-set(S)))

Solution 2:

This is the simplest thing I could come up with:

import random

S=[1,8,93,3,8]
m = max(S)

not_in_S = random.choice([x for x in range(m) if x not in S])