Find a missing number in an integer array [duplicate]

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
– thesentiment, Commented May 10, 2015 at 5:42
use binary search... that is the best you can do... First chapter in Programming Pearls.. — dharam
– dharam, Commented May 10, 2015 at 5: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
– Jan Špaček, Commented May 10, 2015 at 6:11
it's true that if the array is sorted, the solution can be given in log(n) time using binary search — Kostas Kryptos
– Kostas Kryptos, Commented May 10, 2015 at 6:26
Yes, the array is sorted. That's why I avoided the linear search — smbl
– smbl, Commented May 10, 2015 at 6:35

swapyonubuntu · Accepted Answer · 2015-05-10 05:51:22Z

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, 2015 at 5:51

swapyonubuntu

2,1354 gold badges27 silver badges39 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

M.Muzammil Over a year ago

Your program return incorrect result when i input {4,5,6,7,8,10}.

M.Muzammil Over a year ago

imgur.com/1l2efzW

Ishamael · Accepted Answer · 2015-05-10 05:37:21Z

1

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.

answered May 10, 2015 at 5:37

Ishamael

12.8k4 gold badges38 silver badges53 bronze badges

Collectives™ on Stack Overflow

Find a missing number in an integer array [duplicate]

2 Answers 2

2 Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Linked

Related