Find Missing Number in Array

In this blog, we will discuss how to find missing number in array, firstly we’ll discuss the problem statement then we’ll deep dive into Alogirthm, Approaches and solution of missing number in array.

How to Find Missing Number in Array

If an array of length is given, then n-1 has entries in the range of 1 to n. Missing from the provided list is one of the elements. In the provided array, locate the missing number.

Example :

Input

arr=[4,5,2,1]

Output

3

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

Approach 1: Using mathematical formula

We are aware that (n(n+1))/2 is the sum of all items in the range of 1 to n. Now calculate the total of the list’s items; the difference between these two figures indicates the list’s missing number.

Algorithm:

  • Sum the first n natural numbers by using the formula sumtotal=n*(n+1)/2.
  • To keep the total of the array’s items, create the variable sum.
  • The entire array should be traversed.
  • Sum’s value should be updated to sum = sum + array[i]
  • Print sumtotal – sum for the missing number.

Implementation :

#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 abs(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;
}

Explanation: The list of items provided does not include element number 3. Missing number is discovered using the summation method.

Complexity analysis:

  • Time Complexity: O(n) Finding the sum of the items in a given array only requires one traverse.
  • Space Complexity: O(1) No extra space needed.

Modification for overflow:

  • Approach:
  • The strategy is the same, except because integer overflow occurs when n is large, choose one number from the known numbers and deduct it from the provided numbers.
  • Integer overflow won’t ever occur during implementation thanks to this method.
    Algorithm:
  • Make a counter variable a = 2 and a variable sum1 = 1 to hold the missing number.
  • The array should be traversed from start to finish index.
  • Sum1 should now be updated as sum1 – arr[i] + a, and a should now be updated as a++.
  • At the conclusion, print the missing number as a sum1.

Implementation:

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)

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));
    }
}
 
#include <iostream>
using namespace std;

int MissingNumber(int a[],int n)
{
   
    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 };
    int n= sizeof(arr)/sizeof(arr[0]);
    cout<<MissingNumber(arr,n);
    return 0;
}

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)

  • Explanation:
  • Now that a=0,b=0,b = 1 3 4 6 5, (XORing for the provided array) a = 1 2 3 4 5 6 (XORing for items beginning with 1 through n+1, where n is the length of the provided array)
  • A-B will now provide the needed number 2. (XORed with the same values result is zero and only an uncommon number i.e, 2 is returned as the result )

Algorithm :

  • Make a variable b and an iterator a=0.
  • Run a loop from 1 to n times, using a=ai for each iteration.
  • Now execute the specified array’s loop from beginning to finish.
  • B=barr[i] for every iteration
  • Return the missing number back as a-b.

Implementation:

class Main {
    // Function to find missing number
    static int MissingNumber(int arr[])
    {
        int n=arr.length;
  
        int a = 0;
        int b = 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);
    }
}

#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;
}


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

Complexity Analysis:

  • Time Complexity: O(n+n) = O(n)
  • To obtain the value of a, the array just has to be traversed once.
  • And a different traversal is necessary to determine the value of b.
  • Space Complexity: O(1) No extra space is needed for storing any variables.

Approach 3 :Using Hash (Frequency Counter)

Get the frequency of each element in the array using a dictionary, then go over the range from 1 to n and return the one whose frequency is 0.

Algorithm:

  • Initialize a dictionary first.
  • Now add the frequency of each integer in the array to the dictionary.
  • Find the missing number that isn’t in the dictionary by starting your traversal from range 1 to n.
  • A missing number is one that doesn’t appear in the dictionary.

The key benefit over linear search is that a dictionary has an O(1) lookup time compared to a list’s O(n).

Code Implementation

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)

Explanation: When 3 is absent from the provided list of items, dict can be used to locate it.

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)

Subtract the array’s total elements’ sum from the array’s total elements plus n+1.
As an illustration, if arr=[1,2,4,5], then deduct the total number of items from the total number of elements in len(arr)+1.

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)

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 several ways to handle this problem; one can be implemented if it is more suited to the particular issue at hand.
  • All methods deal with O(n) time complexity, although how well they do so largely depends on space optimization methods.
  • As a result, we now know a variety of effective methods for extracting the missing number from the supplied list of items.
  • The XOR (bit manipulation) approach is thought to be the most effective of all of them in terms of space and time complexity.

Leave a Reply

Your email address will not be published. Required fields are marked *