Find a random number NOT in array – code

Find random number not in array is a tricky question. It is pretty straight forward to find a random element in array by getting an random index within the range. If you are asked to find a random element that is NOT in array, your brain might not response quickly as you wish. There is a strategy to solve this kind of question. You just need to think about “negative space”.

There are two steps to solve this kind of “not in” question. First find the complement of the elements. For example, given an array of 5 element, if you have {1,2}, the complement elements are { 3, 4,5}. The second step is simply to find a random number from {3, 4, 5}.

Google Interview Question:
find random number 0,M, that’s not in the array K,
int uniform(int M); -> 0, …, M-1 this function return a random # between 0, M-1




Input array: [1, 3, 4, 6, 9]
Random number not in the array: 7

O Notation:
Time complexity: O(n+k), n is the range of the random number, m in the number of elements in K
Space complexity: O(n)

Find random number not in array (YouTube)

Comments are closed