Coding Interview Question 1: Find the Missing Number

Suppose you have 100 integers, now one of them is missing, so how do you find the missing number using your C programming skills. 

Note: We are requesting to all of you that the first try to solve the program by yourself if you are unable to solve it or find any error then go for the solution.

Example

Suppose an array is given as input: {1, 5,2,4,3,6,8,9,10} and in this array 7 number is missing as output.

Trick 1 (Find the missing number using the formula of the sum)

Algorithm

1. Find the sum of the number, Suppose, there are total x numbers then 

sum_of_numbers = x*(x+1)/2
2. If all the numbers subtract from the sum of the numbers then missing number occur.

Program

#include <stdio.h>
int main()
{
    int arr[]={5,4,9,8,6,1,3,2}; //Initialize Array
    int sum_of_number, x = 9,i, missing_number;
    //Find the Sum of the numbers given in an array
    sum_of_number = (x)*(x+1)/2;
       printf("   sum of the number is %d\n",sum_of_number);
    //Subtract all numbers of given array from the sum of the numbers, total of the numbers is 45, now subtract each number from
    //the sum_of number For example: 45-5 = 40
    // Now subtract 40-4 = 36, 36-9 = 27, 27-8 = 19, 19-6 = 13, 13-1 = 12, 12-3 = 9, 9-2 = 7.
    for (i=0;i<x-1;i++)
    {
        sum_of_number = sum_of_number - arr[i];

        printf ("   sum of number %d \n", sum_of_number);
    }
    //Get missing number
    missing_number = sum_of_number;
    printf ("Get the missing Number is %d\n",missing_number);
    return 0;
}

Output

An output of the Missing Number Program

Trick 2 (Find the missing number using the XOR operator)

1. XOR all the elements of an array store the result into Y1.

2. XOR all the numbers from 1 to x, store the result into Y2.

3. XOR Y1 and Y2 and Get the missing number.

Program

#include <stdio.h>
int main()
{
    int arr[]={1, 2,3,4,5,6,8,9}; //Initialize an array
    int missing_number,i,x=9,Y1,Y2;
     Y1 = arr[0];
     Y2 = 1;

    for (i=1;i<x;i++)
    {
        Y1=Y1^arr[i];
    }

    for (i=2;i<=x+1;x++)
    {
        Y2=Y2^i;
    }
    missing_number = Y1^Y2;
    printf("The Missing Number is %d\n",missing_number);
    return 0;

}

Output

The missing number is 7.