Find Missing Number in Array

Last Updated on November 1, 2023 by Ankit Kochar

Arrays are an essential data structure in computer programming. Arrays are composed of a set of elements, and each element is reachable through an assigned index. Identifying a missing number within an array is a frequent challenge in programming. This article explores various techniques for locating a missing number within an array. Without further ado, let’s proceed to our next section, which covers methods for discovering a missing number in an array.

How to Find Missing Number in Array?

In a sequence of integers represented by an array with a length of n-1, where the integers are confined to the range from 1 to n, a particular number is absent. The objective is to identify and locate the missing number within the array.
Example :

Input

arr=[4,5,2,1]

Output

3

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

Approach 1: Using a Mathematical Formula to Find Missing Number in Array

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.

Code Implementation of Finding Missing Number in Array

#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. The 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 to find missing number in array using mathematical formula

• 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: In 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) to find missing number in array

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 to Find Missing Number in Array using XOR Operator

• 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.

Code Implementation to Find Missing Number in Array using XOR Operator

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: In 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) to Find the Missing Number in Array

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 to Find Missing Number in Array using Hash

• 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 to Find Missing Number in Array using Hash

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 traversals are required, One for populating the dictionary and the other one, to get the element that is missing in the dictionary.
• Space Complexity: O(n) Extra space is required for the 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.

Code 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
In conclusion, finding a missing number in an array is a common and fundamental problem in the realm of programming. Whether dealing with sequences or collections of data, this challenge often arises. It is typically defined within a specified range, such as from 1 to n, where n represents the length of the array minus one. There are various methods available to tackle this problem, ranging from mathematical formulas to bitwise operations and iterative algorithms. The choice of approach may depend on factors like the array’s size and performance requirements, with efficiency being a crucial consideration. Additionally, it’s vital to consider edge cases and validate algorithms with test cases to ensure their correctness and reliability. By mastering these methods and approaches, programmers can effectively address the task of finding a missing number in an array, enhancing data integrity and accuracy within their applications.

FAQs related to Find Missing Number in Array

Here are some frequently asked questions related to finding the missing number in array.

1. What is the most common approach to finding a missing number in an array?
The most common approach is to use the mathematical formula for the sum of a series, which involves calculating the expected sum of all numbers in the range and subtracting the actual sum of the array elements. This approach is efficient and widely used.

2. Can the missing number be anywhere in the array?
Yes, the missing number can be at any position within the array. It’s essential to consider this possibility when designing your algorithm.

3. Are there any special considerations when the range is not from 1 to n?
If the range is not from 1 to n, you will need to adjust your algorithm to account for the specific range. You can calculate the expected sum for that range and apply the same principles.

4. What if the array contains duplicates?
If the array contains duplicate values, it may affect your approach. Ensure that your algorithm is designed to handle duplicates, either by eliminating them or by employing a more advanced technique to find the missing number.

5. Is there a difference in performance between the various methods?
Yes, there can be differences in performance between different methods. Mathematical formulas are generally the most efficient, while iterative methods may be slower for large arrays. The choice of method should consider the size of the array and specific requirements.

Some similar blogs

• Kth Smallest array in an array
• subarray with given sum