Question 11 : Find missing number in the array.

You are given an integer array containing 1 to n but one of the numbers from 1 to n in the array is missing. You need to provide the optimum solution to find the missing number. 

The number cannot be repeated in the array.:

int[] arr1={7,5,6,1,4,2};
Missing numner : 3

int[] arr2={5,3,1,2};
Missing numner : 4

Solution:

1. Find the sum of n number using formula n=n*(n+1)/2
2. Find the sum of elements present in given array.
3. Substract (sum of n numbers – sum of elements present in the array).

Java program to find missing number in an array:

public class MissingNumberMain {
 
    public static void main(String[] args) {
 
        int[] arr1={7,5,6,1,4,2};
        System.out.println("Missing number from array arr1: "+missingNumber(arr1));
        int[] arr2={5,3,1,2};
        System.out.println("Missing number from array arr2: "+missingNumber(arr2));
 
    }
 
    public static int missingNumber(int[] arr)
    {
        int n=arr.length+1;
        int sum=n*(n+1)/2;
        int restSum=0;
        for (int i = 0; i < arr.length; i++) {
            restSum+=arr[i];
        }
        int missingNumber=sum-restSum;
        return missingNumber;
    }
}

When you run the above program, you will get the below output:

Missing number from array arr1: 3
Missing number from array arr2: 4

  
    
    
    
    
  

  

    
Approach
    
Time Complexity
    
Space Complexity
    
Best Use
  

  

    

      XOR method
    
    

      O(n)
    
    

      O(1)
    
    

      ⭐ Best & overflow-safe
    
  

  

    

      Sum formula (Math)
    
    

      O(n)
    
    

      O(1)
    
    

      Simple but may overflow
    
  

  

    

      Hashing / boolean array
    
    

      O(n)
    
    

      O(n)
    
    

      Easy to understand
    
  

  

    

      Sorting the array
    
    

      O(n log n)
    
    

      O(1) / O(n)
    
    

      ❌ Not optimal