Find nth number that doesn't exist in a set

Question

Given a set of skipped numbers I need to find an Nth number that doesn't exist in the set. Example: Given a set [1, 4, 5] some results: For N = 1 result 0 For N = 2 result 2 (because 1 is skipped) For N = 3 result 3 (because 1 is skipped) For N = 4 result 6 (because 1,4,5 get skipped) This should work for fairly large N, so the straightforward solution doesnt quite cut it sadly =(

Accepted Answer

One way to do this is to build up an auxiliary array telling you, for each index in the array, the number of values below it that are missing. For example, in this array:

```
1 4 5 9 13  (Array A)
```

this array would be

```
1 4 5 9 13  (Array A)
1 3 3 6 9   (Array B)
```

You can fill in Array B in time O(n) using the following approach:

- B[0] = A[0] (do you see why?)

- B[n + 1] = B[n] + A[n + 1] - A[n] - 1. This looks cryptic, but is actually pretty straightforward. The number of total values missing before position n + 1 is given by the number of values missing before position n (that's B[n]), plus the number of elements missing between positions A[n + 1] and A[n]. That value is A[n + 1] - A[n] - 1.

There's an important observation you can make now: for any position i, the value of A[i] is given by B[i] + i. (Check this out above). Why is this? Well, for any position i, the number of numbers missing below it is B[i]. There's also i numbers before it, which means that the total number of values less than it is B[i] + i.

Now that you have this, you can answer queries of the form "what's the kth missing number?" in time O(log n) by using the following algorithm:

- Do a binary search in the B array (note that it's sorted!) to find the first value strictly greater than k.

- If that entry occurs at position 0, then the answer is k. The reason for this is that you're looking for the kth smallest missing number in the array, and k was smaller than the first entry in the array. Therefore, the number you want is k itself.

- If that entry occurs elsewhere (say, position x), then you know x ≠ 0, so there's some position right before it, which is position x - 1. Since B[x - 1] ≤ k, you know that the value you want must come between A[x - 1] and A[x]. If you then subtract out B[x] from k, you get back the index of the missing number between A[x - 1] and A[x]. Therefore, your missing number is A[x - 1] + k - B[x - 1] + 1.

For example, let's take the earlier array:

```
1 4 5 9 13  (Array A)
1 3 3 6 9   (Array B)
```

Suppose we want the 5th smallest missing value. Doing our binary search finds this spot:

```
1 4 5 9 13  (Array A)
1 3 3 6 9   (Array B)
      ^
```

Backing up one spot takes us here:

```
1 4 5 9 13  (Array A)
1 3 3 6 9   (Array B)
    ^
```

The answer should be A[i] + k - B[i] + 1. This is 5 - 3 + 5 + 1 = 8. This is correct:

- The 0th missing element is 0

- The 1st missing element is 2

- The 2nd missing element is 3

- The 3rd missing element is 6

- The 4th missing element is 7

- The 5th missing element is 8.

Let's do another: suppose we want the 6th. The binary search takes us here:

```
1 4 5 9 13  (Array A)
1 3 3 6 9   (Array B)
        ^
```

Back up a spot:

```
1 4 5 9 13  (Array A)
1 3 3 6 9   (Array B)
      ^
```

We want A[i] + k - B[i] + 1 = 9 + 6 - 6 + 1 = 10. That's indeed the correct answer.

Overall, this is O(n) preprocessing, and queries can be solved in time O(log n) each.

Hope this helps!

Find nth number that doesn't exist in a set

Solution

Problem

Related problems