Find out missing number in an array in Java

Recently, I went through an interview in an IT MNC company, there interviewer asked me this question. He asked me "I have an array of numbers from 1 to 100. The numbers are in random order in the array, and 1 number is missing. I have to find out the missing number.".

This type of question is generally asked in interview to check candidate logical and analytical skills to handle a problem. I gave him the answer but that wasn't an optimized one. He asked me to think again, but I couldn't think about the optimized solution.

Then, I tried to find out the solutions on internet and found few good algorithms to solve this problem. Let's see the solutions of this problem:

Solution 1

You can do this in O(n). The sum of natural numbers from 1 to N, is expressed by mathematical formula: Nx(N+1)/2. Iterate through the array and compute the sum of all numbers. Since, we have 100 number then the value of N is 100 (i.e. N = 100). Subtract the sum of the array from N x(N+1)/2, where N=100.

//the sum of the numbers in the array.
int sum = 0;
int index = -1;
for (int i = 0; i < arr.length; i++) {
    if (arr[i] == 0) {
         index = i; 
    } else {
         sum += arr[i];
    }
}

//the total sum of numbers between 1 and arr.length.
int total = (arr.length + 1) * arr.length / 2;

System.out.println("missing number is " + (total - sum) + " at index " + index);

Solution 2

for (int index = 0; index < numbers.length; index++) {
    if (numbers[index] != index+1){
        System.out.println(index+1);
    }
}

Solution 3

/* getMissingNumber takes array and size of array as arguments*/
int getMissingNumber (int arr[], int num)
{
    int i, total;
    total  = (num + 1)*(num + 2)/2;   
    for ( i = 0; i< num; i++)
       total -= arr[i];
    return total;
}

Solution 4

/* getMissingNumber takes array and size of array as arguments*/
int getMissingNumber (int arr[], int num)
{
    int i;
    /* For xor of all the elemets in arary */
    int x1 = a[0]; 
    /* For xor of all the elemets from 1 to n+1 */
    int x2 = 1; 
     
    for (i = 1; i< n; i++)
        x1 = x1^a[i];
            
    for ( i = 2; i <= n+1; i++)
        x2 = x2^i;         
    
    return (x1^x2);
}

I think I tried my best to provide the solution to the problem. If you think that there can be more then please feel free to post your comments, suggestions and feedback to make the content a valuable one.