Missing Number in Array

You are given with the array of length n-1 and elements ranging from 1 to n, you have to figure out the missing number.

Scope

This article tells how to find the missing number in the array

In this article we will learn finding missing number using mathematical approch

In this article we will learn complexity to find the missing number

In this article we will learn Modification for overflow

Takeaways

The best meathod to find the missing number is XOR(bit manipulation).

How to print a missing number in array?

Given an array of length, n-1 consists of elements from range 1 to n. One of the elements is missing from the given list. Find the missing number in the given array

Example :

Input : arr=[4,5,2,1]
    Output: 3

Example Explanation:

Missing number from range 1 to 5 is 3 from the given list of numbers

Constraints:

• n == nums.length
• 1 <= n <=10^4
• 0 <= nums[i] <= n
• All the numbers of nums are unique.

Approach 1: Using mathematical formula

Approach :

We know that the sum of elements from range 1 to n is: $\frac{(n(n+1)}{2}$ . Now find the sum of the elements from the given list, the difference between these two values gives the missing number from the given list.

• Algorithm :

1. Calculate the sum of first n natural numbers as sumtotal= $\frac{n*(n+1)}{2}$
2. Create a variable sum to store the sum of array elements.
3. Traverse the array from start to end.
4. Update the value of sum as sum = sum + array[i]
5. Print the missing number as sumtotal – sum

• Implementation :
  

Python :

def MissingNumber(arr):![](https://hackmd.io/_uploads/HkThSlMYq.jpg)

        sum1+=arr[i]
    total=(n(n+1))//2
    missingnum=total-sum1
    return(missingnum)
#Driver Program
if __name__=='__main__':
    arr=[ 1, 2 , 4 , 5 , 6 ]
    ans=MissingNumber(arr)
    print(ans)

Java:

import java.util.*;
import java.util.Arrays;
class Solution {
    public static int
    // Function to get missing number
    MissingNumber(int[] arr)
    {
        int n=arr.length;
        int sum1=((n)*(n+1))/2;
        int sum2;
        for(int i=0;i<n;i++)
          sum2+=arr[i];
        return sum1-sum2;
    }
    public static void main(String[] args)
    {
        int[] arr = { 1, 2, 4, 5, 6 };
        System.out.println(MissingNumber(arr));
    }
}

C++:

#include <bits/stdc++.h>
using namespace std;
 
// Function to get the missing number
int MissingNumber(int a[], int n)
{
 
    int total = (n) * (n +1)/ 2;
    for (int i = 0; i < n; i++)
        total -= a[i];
    return total;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 4, 5, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int ans = MissingNumber(arr, n);
    cout << ans;
}

• Output :

       3

• Explanation: Number 3 is missing from the given list of elements.Using summation formula missing number is obtained

Complexity analysis:

• Time Complexity : O(n) Only one traversal needed to find the sum of elements in given array.
• Space Complexity : O(1) No extra space needed.

Modification for overflow:

• Approach :
  • The approach remains the same but integer overflows when n is large, to avoid integer overflow, pick one number from known numbers and subtract one number from given numbers.
  • This way there won’t have Integer Overflow ever during implementation.
• Algorithm :

1. Create a variable sum1 = 1 which will store the missing number and a counter variable a = 2.
2. Traverse the array from start to end index .
3. Update the value of sum as sum1 = sum1 – arr[i] + a and update a as a++.
4. Print the missing number as a sum1 in the end .

Python :

def MissingNumber(arr):
    i, sum1 = 0, 1
    n=len(arr)
    for i in range(2, n + 2):
        sum1 += i
        sum1 -= arr[i - 2]
    return sum1
 
# Driver Code
if __name__=='__main__':
    arr=[ 1, 2 , 5 , 3 ]
    ans=MissingNumber(arr)
    print(ans)

Java:

class Solution {
    static int MissingNumber(int arr[])
    {
        int n=arr.length;
        int total = 1;
        for (int i = 2; i <= (n + 1); i++) {
            total += i;
            total -= arr[i - 2];
        }
        return total;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] arr = { 1, 2, 5, 3 };
        System.out.println(MissingNumber(arr));
    }
}
 

C++:

#include <stdio.h>
 
int MissingNumber(int arr[])
{
    int n= sizeof(arr)/sizeof(arr[0]);
    int i, total = 1;
 
    for (i = 2; i <= (n + 1); i++) {
        total += i;
        total -= a[i - 2];
    }
    return total;
}
 
// Driver Program
int main()
{
    int arr[] = { 1, 2, 5, 3 };
    printf("%d",MissingNumber(arr));
    return 0;
}

• Output :

        4

Explanation the given range [1,5], 4 is missing from the array.

Complexity Analysis:

• Time Complexity: O(n) Only one traversal is required
• Space Complexity : O(1) No extra space needed

Approach 2: Using Bit manipulation(XOR)

• Approach:

This property can be better explained using this image (Please create such image) Image 1: 

• Example :

        Input:
        arr=[1,3,4,6,5]
        Output: 2

• Explanation: Now a=0,b=0
  • * b = `1^ 3 ^ 4 ^ 6 ^ 5` (XORing for given array) a = `1^ 2 ^ 3 ^ 4 ^ 5 ^ 6` (XORing for elements starting from `1` to `n+1`, n is length of given array)
  • * Now a^b : will give missing number `2` (XORed with same values result is zero and only uncommon number i.e , `2` is returned as the result )

Algorithm :

1. Create a iterator a=0 and a variable b
2. Run a loop from 1 to n
3. For every iteration a=a^i
4. Now run a loop from start to end in given array
5. For every iteration b=b^arr[i]
6. Return the missing number as a^b

Implementation:

Python :

def MissingNumber(arr):
    n=len(arr)
    a,b-0,0
    for i in range(1,n+1):
        a=a^i
    for i in range(n):
        b=b^arr[i]
    return a^b
#Driver Code:
if __name__=='__main__':
    arr=[1,2,5,3,4,7]
    ans=MissingNumber(arr)
    print(ans)

Java:

class Main {
    // Function to find missing number
    static int MissingNumber(int arr[])
    {
        int n=arr.length;
        int x1 = 0;
        int x2 = 0;
 
        /*For xor of all the elements in array */
        for (int i = 1; i <n; i++)
            a = a ^ arr[i];
 
        /* For xor of all the elements from 1 to n+1 */
        for (int i = 1; i < n + 1; i++)
            b = b ^ i;
 
        return (a ^ b);
    }
 
    /* program to test above function */
    public static void main(String args[])
    {
        int a[] = { 1, 2, 4, 5, 6 };
        int ans = MissingNumber(a);
        System.out.println(ans);
    }
}

C++:

#include <bits/stdc++.h>
using namespace std;
 
// Function to get the missing number
int MissingNumber(int arr[])
{
    // For xor of all the elements in array
    int a = 0;
    int n= sizeof(arr)/sizeof(arr[0]);
    // For xor of all the elements from 1 to n+1
    int b = 0;
 
    for (int i = 0; i < n; i++)
        a =a ^ arr[i];
 
    for (int i = 1; i <= n; i++)
        b = b ^ i;
 
    return (a ^ b);
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 4, 5, 6 };
    int ans = MissingNumber(arr);
    cout << ans;
}

• Output:

        3

Explanation the given range [1,6], 3 is missing from the array.

Complexity Analysis :

• TIme Complexity : O(n+n) = O(n)
  • Only one traversal of the array is required for getting value of a
  • And another seperate traversal is required for getting value of b.
• Space Complexity : O(1) No extra space is needed for storing any variables.

Approach 3 :

Using Hash (Frequency Counter)

Approach :

Using a dictionary get the frequency of each element in the array and traverse the from 1 to n and return the element whose frequency is found to be 0.

Algorithm :

1. Firstly initialise an dictionary.
2. Now populate the dictionary with frequency of each number in array
3. Now start traversing from range 1 to n and find the missing number which is not present in the dictionary.
4. Missing number is the number which is not present in dictionary.

Dictionary has a lookup time of O(1) in contrast to list with O(n), this is the main advantage while compared to linear search.

Implementation:

Python:

// we need to import to get counter function
from collections import Counter
def MissingNumber(nums):
    count = Counter(nums)
    for i in range(len(nums)+1):
        if(not count.get(i)):
            return i
#Driver Program
if __name__=='__main__':
    arr=[ 1, 2 , 4 , 5 , 6 ]
    ans=MissingNumber(arr)
    print(ans)

The above code without using inbuilt counter method is as follows: Python:

def MissingNumber(nums):
    # initialise dictionary 
    dictionary={}
    for i in nums:
        #if i is not found add it to dictionary with its frequency as 1.
        if i in not in nums:
            dictionary[i]=1
        # if i is found then increase its frequency by 1.
        else:
            dictionary[i]+=1
    #Now checking for number which is missing in dictionary from given range
    for i in range(1,len(nums)+2):
        if i not in dictionary:
            return(i)
#Driver Program
if __name__=='__main__':
    arr=[ 1, 2 , 4 , 5 , 6 ]
    ans=MissingNumber(arr)
    print(ans)

            

• Output:

        3

• Explanation: 3 is missing from the given list of elements, it can be found by using dict.

Complexity Analysis:

• Time Complexity: O(n+n) = O(n) Two traversels are required, One for populating dictionary and the other one, to get the element which is missing in dictionary.
• Space Complexity : O(n) Extra space is required for dictionary.

Approach 4:(Used only for Python)

• Approach:Take the sum of all elements in the array and subtract that from the sum of n+1 elements.For Example : If arr=[1,2,4,5] then take the sum of all elements in arr and subtract that from the sum of len(arr)+1 elements.
• Implementation:

def MissingNumber(arr):
    n=len(arr)
    sum1=n*(n+1)//2
    return sum1-sum(a)
 
 
# Driver program to test above function
if __name__=='__main__':
 
    a = [1, 2, 4, 5, 6]
    n = len(a)+1
    ans = MissingNumber(a)
    print(ans)

• Output:

      3 

• Explanation : From the given range [1,6], 3 is missing from the array.

Complexity Analysis:

• Time Complexity : O(n) Only one traversal is required for finding the missing number in the array.
• Space Complexity : O(1) No extra space is needed.

Conclusion

• There are many approaches available to solve this problem, an approach which is more suitable for the given problem can be applied.
• All the approaches deal with O(n) time complexity but depend it mainly depends on the space optimization techniques.
• To conclude, we have learned various optimized techniques on how to get a missing number from the given list of elements.
• Out of all these methods, XOR (bit manipulation) method is considered to be more efficient in both space and time complexity.