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

** Java Code:**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
import java.util.*; public class RandomNumNotInK2 { //Find random number not in array K, Time O(n+k), Space O(n), k is array K length. public static int randomNotInK(int n, int[] K) { Set<Integer> set = new HashSet<Integer>(); for (int i = 0; i < n; i++) set.add(i); for (int i = 0; i < K.length; i++) set.remove(K[i]); int un = randomInt(set.size()); List<Integer> list = new ArrayList<>(set); return list.get(un); } //Generate random number between 0 ~ n-1, Time O(1), Space O(1) public static int randomInt(int n) { Random rand = new Random(); return rand.nextInt(n); } public static void main(String[] args) { int n = 10; int[] K = {1, 3, 4, 6, 9}; System.out.print("Input array: "); System.out.println(Arrays.toString(K)); System.out.println("Random number not in the array: " + randomNotInK (n, K)); } } |

**Output:**

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)

**Note:**

If you have any questions or want to put comments, please post at youtube. I will answer you!

The code displayed here is the simplified version after the enhancement in the 2nd edition of Java coding interview pocket book. Please click the top download button to download the original version.

Download FindRandomNotInK.java

Find random number not in array (YouTube)

The complete list of coding interview questions