Find The Missing Number

Problem Statement

You are given an array of integers of size N – 1 ranging from 1 to N. There are no duplicates in the list. One of the integers is missing in the array. The task is to find the missing number in the series.

Examples:

Input: list[] = {1, 2, 4, 6, 3, 7, 8,10,5}
Output: 9
Explanation: The missing number from 1 to 10 is 9.

Input: list[] = {3, 2, 4, 5}
Output: 3
Explanation: The missing number from 1 to 5 is 1.

Simple Approach

This method uses the formula of summation.

The size of the array is N – 1. So the sum of n elements, that is the sum of numbers from 1 to N can be calculated by using the formula N * (N + 1) / 2. Now find the summation of all elements in the array and subtract it from the summation of first N natural numbers, the value obtained will be the value of the missing element.

Algorithm:

• Calculate the summation of first N natural numbers as Total = N * (N + 1) / 2
• Create a variable sum to store the summation of elements of the array.
• Iterate the array from start to end.
• Updating the value of sum as sum = sum + array[i]
• Print the missing number as the Total – sum

C Implementation

int MissingNo(int a[], int n) {
  int i, total;
  total = (n + 1) * (n + 2) / 2;
  for (i = 0; i < n; i++)
    total -= a[i];
  return total;
}

Java Implementation

MissingNumbers(int[] arr) {
  for (int i = 0; i < arr.length; i++) {
    int index = Math.abs(arr[i]);
    if (arr[index - 1] > 0) {
      arr[index - 1] *= -1;
    }
  }
  List < Integer > ans = new ArrayList < > ();
  for (int i = 0; i < arr.length; i++) {
    if (arr[i] > 0) {
      ans.add(i + 1);
    }
  }
  return ans; 
}

Python Implementation

def MissingNo(arr):
    n = len(arr)
    total = (n + 1)*(n + 2)/2
    arr_sum = sum(arr)
    return total - arr_sum

Time Complexity: O(N) where N is the size of the array.
Space Complexity: O(1) because no extra space is needed.

XoR Approach

This method uses the technique of XOR to solve the problem.

Approach: XOR has certain properties Assume
a1 ^ a2 ^ a3 ^ …^ an = A1 and a1 ^ a2 ^ a3 ^ …^ an-1 = A2, Then A1 ^ A2 = an

Algorithm:

• Create two variables a1= 0 and a2 = 0
• Iterate from 1 to n with i as the counter.
• For every index i update a1 as a1 = a1 ^ i
• Now iterate over the array from start to end.
• For every index i update a2 as a2 = a2 ^ arr[i]
• Print the missing number as a1 ^ a2.

Dry Run of XoR Approach

C Implementation of XoR Approach

int MissingNo(int arr[], int n) {
  int x1 = arr[0];
  int x2 = 1;

  for (int i = 1; i < n; i++)
    x1 = x1 ^ arr[i];

  for (int i = 2; i <= n + 1; i++)
    x2 = x2 ^ i;

  return (x1 ^ x2);
}

Java Implementation of XoR Approach

static int MissingNo(int arr[], int n) {
  int x1 = arr[0];
  int x2 = 1;

  for (int i = 1; i < n; i++)
    x1 = x1 ^ arr[i];

  for (int i = 2; i <= n + 1; i++)
    x2 = x2 ^ i;

  return (x1 ^ x2);
}

Python Implementation of XoR Approach

def MissingNo(arr, n):
    x1 = arr[0]
    x2 = 1
     
    for i in range(1, n):
        x1 = x1 ^ arr[i]
         
    for i in range(2, n + 2):
        x2 = x2 ^ i
     
    return x1 ^ x2

Time Complexity: O(N) where N is the size of the array because only one traversal is needed.
Space Complexity: O(1) because no extra space is needed.

Practice Questions

First Missing Integer
Repeat and Missing Number Array

Frequently Asked Questions

What are the constraints of this problem?
All the numbers in the array should be between 1 to N, where N -1 is the size of the array.

Will these approaches work for larger numbers?
No, it will only work for numbers less than 10^6 because we can not make an array of greater size.