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
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 | 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)); } } |
JavaScript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | //Time O(1), Space O(1) function uniform(max) { return Math.floor(Math.random() * max); } // K is sorted list, N is range of numbers //Time O(N+K), Space O(N) function randomNotInK(N, K) { uSet = new Set(); for (let i = 0; i < N;i++) { uSet.add(i); } for (let j of K) { uSet.delete(j); } var list = Array.from(uSet); let un = uniform(list.length); return list[un]; } var k= [1,3,4,6,9]; var r = randomNotInK (15, k); console.log("randome number not in K:\t " + r); |
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | import random # Time O(1) Space O(1) def uniform(max) : return random.randrange(max) # K is sorted list, N is range of numbers # Time O(N+K), Space O(N) def randomNotInK(N, K) : uSet = set() for i in range(0, N) : uSet.add(i) for j in K: uSet.remove(j) res = list(uSet) un = uniform(len(res)) return res[un] k = [1,3,4,6,9] r = randomNotInK (15, k) print("randome number not in K: " + str(r)) |
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)
Download FindRandomNotInK.java
Find random number not in array (YouTube)
