Description: We are given a list of ‘n-1’ numbers, all lying between 1 to n. We have to find the number that lies between 1 and n, but isn’t present in the list.

 

If video does not load, Click here

Example:

Input:

1  2  3  5  6

Output:

4

Algorithm:

Method 1:Using summation of natural nos

1.Calculate sum of all elements in the list and store value in ‘x’.

2.Sum of first ‘n’ natural nos is given by:

                                y=n*(n+1)/2

3.Missing number:  y - x

Time Complexity: O(n)

Method 2:Using xor

1.    Intialize x=0 and y=0.

2.    Perform bitwise xor of all number from 1 to n using variable ‘x’.

3.    Perform bitwise xor of all numbers present in the list using variable ‘y’.

4.    Missing no: x (xor) y

Time Complexity:O(n)

Implementation in C:

/*The following function returns missing number using Method 1.*/

int get_missing_number (int arr[], int n)
{
    int i, total;
    total = (n)*(n+1)/2;   
   /*Sum of first n natural numbers*/
    for ( i = 0; i< n-1; i++)
       total -= arr[i];
    return total;/*return missing number*/
}
Go to top