Missing number in array

Photo by Dmitry Bukhantsov on Unsplash

Company Tags

#Flipkart #MorganStanley #Accolite #Amazon #Microsoft #D-E-Shaw

#OlaCabs #Payu #Visa #Intuit #Adobe #Cisco #Qualcomm

Given an array of size N-1 such that it only contains distinct integers in the range of 1 to N. Find the missing element.

Example 1:

Input:
N = 5
A[] = {1,2,3,5}
Output: 4

Example 2:

Input:
N = 10
A[] = {6,1,2,8,3,4,7,10,5}
Output: 9

Your Task :
You don’t need to read input or print anything. Complete the function MissingNumber() that takes array and N as input parameters and returns the value of the missing number.

Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)

Constraints:
1 ≤ N ≤ 106
1 ≤ A[i] ≤ 106

Approach 1 (Using summation of first N natural numbers): The idea behind the approach is to use the summation of the first N numbers.

Find the sum of the numbers in the range [1, N] using the formula N * (N+1)/2. Now find the sum of all the elements in the array and subtract it from the sum of the first N natural numbers. This will give the value of the missing element.

class Solution {
     public static int getMissingNo(int[] nums, int n)
    {
        int sum = ((n + 1) * (n + 2)) / 2;
        for (int i = 0; i < n; i++)
            sum -= nums[i];
        return sum;
    }

    // Driver code
    public static void main(String[] args)
    {
        int[] arr = { 1, 2, 3, 5 };
        int N = arr.length;
        System.out.println(getMissingNo(arr, N));
    }
}

Approach 2(Using Sorting)

Eg 2,3,1,5 sort the array to 1,2,3,5 then index of array element will be equal to array value — 1 at that particular index so the index where this condition fails is the answer……answer can be found by returning i+1.

class Solution {
    int missingNumber(int array[], int n) {
        // Your Code Here
        int res = 0;
        
        
        Arrays.sort(array);
        
        for(int i=0;i<array.length;i++){
            if(array[i] != i+1){
                res = i+1;
                break;
            }
        }
        
        if(res == 0){
            res = n;
        }
        
        return res;
    }
}