-3

I want to get the first missing number in a range of millions of numbers. For example, I have an array with n number of elements. And it starts from 0. And in between for example, after 4380, 4381 is missing and is continued with 4382. So, how can I find that 4381?

I have seen this questions on many sites including SO, Quora and many more. But, all I could find was with a small range of numbers. For which, a for loop is the best choice. But, when we have millions of numbers in an array, then this wont be both time and memory efficient. What can be used in this case to get it done having both the time and memory in consideration?

NOTE: The elements are ordered in ascending order

Gustavo Pagani
  • 6,583
  • 5
  • 40
  • 71
Sambhav Khandelwal
  • 3,585
  • 2
  • 7
  • 38
  • Does the order of the elements matter? – MC Emperor Dec 06 '22 at 15:10
  • The elements are alredy ordered in ascending order. Thanks @MCEmperor for bringing to my notice. I will update my question – Sambhav Khandelwal Dec 06 '22 at 15:11
  • 4
    Start from the middle of array, and check if the value at that position is the expected value. If yes, the missing value is somewhere between current index and end of the array. If no, the missing value is somewhere between beginning of array and current index. Repeat, but using the new range. Whittle down until the range has one element. , e.g., binary search. – Andrew S Dec 06 '22 at 15:14

1 Answers1

6

So when you have a sorted array of n elements starting at 0 then there is a clear correlation between an element's index and value (assuming there can be no duplicates):

index   value
0       0
1       1
2       2
...
100     100

So you can use a binary-search approach and check e.g. the element at length / 2. If the value is greater than its index, there has to be a missing number somewhere below.

index   value
0       0
1       1
2       2
...
100     100
101     102
102     103
...
204     205

In this example, if you would check index 102 you would see a value of 103, so between index 0 and 102 there has to be a missing number. Now, repeat the algorithm for the sub-array 0..101 until you have found the missing element. Otherwise, proceed with the other half.

If elements do not start at 0 it would be easy to add a constant value everywhere.

If there can be arrays without a missing number, you can also start by comparing the last element and abort immediately if the value is equal to its index.

Basil Bourque
  • 303,325
  • 100
  • 852
  • 1,154
Marvin
  • 13,325
  • 3
  • 51
  • 57