Array [1,2,3....n]. A number is missing in that series. What is the optimum way to find out that number?

Question

There will be an array starting from 1,2,3.... n. If any one number is removed from the array what is the optimun way to find out removed number.

So you are given an array with n-1 length or one number is duplicate here? — Dau, Nov 20 '19 at 04:55
Try geeksforgeeks solution https://www.geeksforgeeks.org/find-the-missing-number/ — Prabhjot Singh Kainth, Nov 20 '19 at 04:58
yes..think of it like a [1,2,3,4,6,7]. 5 is missing. What is the optimum way to find out the missing 5. — Giri Aakula, Nov 20 '19 at 04:58
If the array is sorted, you just iterate through the array until you find two elements that are adjacent, but not consecutive. — user3386109, Nov 20 '19 at 05:17

score 1 · Answer 1 · answered Nov 20 '19 at 08:59

The following is just one possible way to find the missing one.

If n is given, then the sum of the series 1 + 2 + 3 + ... + n is,

S =  1 + 2 + 3 + ... + n
  = n * (n + 1) / 2

So, ultimately, you know the value of S. Now sum up all the integers you are given. Let's call it S'. And the difference between S and S', (S - S') is the answer.

This will work even the given integers are in random order. This will not require a binary search where it is required that the integers must be sorted and needs an extra nlogn time.

score 0 · Answer 2 · answered Nov 20 '19 at 04:56

0

Assuming that the numbers are in serial order

Two solutions

Check while reading.
Binary search for the missing number.

answered Nov 20 '19 at 04:56

a-c-sreedhar-reddy

568
4
14

score 0 · Answer 3 · answered Nov 20 '19 at 19:00

If the array is sorted then the element can be found in O(log n) time and O(1) space

Using Binary Search.

int search(int *ar, int n) { 
    int a = 0, b = n - 1; 
    int mid; 
    while ((b - a) > 1) { 
        mid = a + ((b-a) >> 1); 
        if ((ar[a] - a) != (ar[mid] - mid)) 
            b = mid; 
        else if ((ar[b] - b) != (ar[mid] - mid)) 
            a = mid; 
    } 
    return (ar[mid] + 1); 
}

If the array is not sorted

n*(n+1)/2 - sum(array)

where n is the length of the array.

Array [1,2,3....n]. A number is missing in that series. What is the optimum way to find out that number?

3 Answers3