Finding Missing number in an array using XOR operation in Java

In this Java tutorial, we gonna learn how to find a missing number in an array in Java using XOR operation.

Problem Statement

We are given an array of ‘n-1’ elements and these elements are in the range from 1 to n. There are no duplicates in the array. One of the integer is missing in array. We have to find the missing number in array.

In this Java tutorial, we are going to find that missing number in array using XOR operation on array elements.

Why XOR operation?

This problem can be solved in a few other ways also, like using two for loop, or subtracting the sum of all elements of array from the sum of all elements in range 1 to n. This will give the missing number.

We will use XOR operation for this problem because if the sum of numbers goes beyond maximum allowed integers, then there can be integer overflow and we may not get the correct answer. So, XOR operation gives correct value in this case.

Algorithm

1. XOR all the array elements, let the result of XOR be a.
2. XOR all numbers from 1 to n, let XOR be b.
3. XOR of a and b gives the missing number.

Java code to find the missing number

import java.util.Scanner;
import java.util.*;

class Codespeedy
{
    public static int result(int arr[] , int n)
    {
        int a=1,b=1;
        
        for(int i=0;i<n-1;i++)
            a=a^arr[i];
        
        
        for(int i=1;i<=n;i++)
            b=b^i;
           
           return a^b;
        
    }
    
    
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        
           int n=scan.nextInt();
           
           int arr[] = new int[1000];
            
            for(int i=0;i<n-1;i++)
            {
                int x=scan.nextInt();
                  arr[i]=x;
            }
            
            System.out.println(result(arr,n));
    }
    
}

INPUT

3
1 2 4

OUTPUT

3

In the example above, the missing number is 3 in the range from 1 to 4.

You may also learn,

• Checking for Duplicacy in an array using Hashing Technique in Java
• How to reverse two dimensional array in Java