Find a missing number in an integer array

Question

I am given a supposedly consecutive array such as this:

{4,5,7,8,9,10} // missing 6

And I am supposed to efficiently find the missing 6.

I have thought of doing a binary search, and checking the mid +1, mid -1.

But I keep thinking there would be so many base cases. I keep failing...

This shouldn't be such a hard problem but I do not know why I am struggling so hard :/

Could someone guide me through this one??

Thanks so much guyz

Although you have already received several possible answers, I think it's worth noting that if you're struggling with one approach, you'll need to move on to figuring out a different one. A binary search likely isn't what they are looking for there. There are a lot of tricks to address the issue, but the simplest one to understand (IMHO) involves a single for loop. — thesentiment, May 10 '15 at 05:42
use binary search... that is the best you can do... First chapter in Programming Pearls.. — dharam, May 10 '15 at 05:54
The array in this question is _sorted_, while the array in referenced question is explicitly shuffled. This allows for a quicker, binary-search solution. — Jan Špaček, May 10 '15 at 06:11
it's true that if the array is sorted, the solution can be given in log(n) time using binary search — Kostas Kryptos, May 10 '15 at 06:26
Yes, the array is sorted. That's why I avoided the linear search — smbl, May 10 '15 at 06:35
Here is your solution in log(n) time http://stackoverflow.com/questions/2113795/quickest-way-to-find-missing-number-in-an-array-of-numbers/30148865#answer-30148865 — Kostas Kryptos, May 10 '15 at 07:43

score 2 · Answer 1 · answered May 10 '15 at 05:51

2

Always keep it simple buddy . You can always do this in N time complexity.

int[] arr = new int[]{4,5,7,8,9,10};
        int missing=0;
        for(int i=0;i<arr.length;i++)
        {  

            int x = arr[++i];
            int y = arr[i] +1;

          if(x != y )
          {
              missing = y;
              break;
          }
        }

        System.out.println(missing);

answered May 10 '15 at 05:51

swapyonubuntu

1,952
3
25
34

Your program return incorrect result when i input {4,5,6,7,8,10}. – M.Muzammil Dec 09 '18 at 12:21
https://imgur.com/1l2efzW – M.Muzammil Dec 09 '18 at 12:22

score 1 · Answer 2 · answered May 10 '15 at 05:37

In one linear pass find the smallest element, the largest element and the sum of all the elements.

Knowing the smallest and the largest you can compute the sum of all the numbers if nothing was missing (it's a sum of an arithmetic progression). Subtracting the actual sum from it will give you the missing number.

Find a missing number in an integer array

2 Answers2