Home » Algorithms

Find the missing number

Find the missing number: In this tutorial, we will learn an advance algorithm to find a missing number in an array of length n range from 1 to n. By Radib Kar Last updated : August 21, 2023

Table of Contents

• Problem statement
• Solution
• Algorithm
• C Implementation
• Output
• Time and Space Complexity

Problem statement

We are given a list of n-1 integers and the integers range from 1 to n. There are no duplicates in the list. Only one of the integer from 1 to n is missing. We need to find the missing number in O(n) time complexity.

Solution

The simplest solution is to take each number from 1 to n and to check whether it exists in the array or not. But such approach has O(n²) time complexity. Thus we need to find some advance algorithm to reduce the time complexity.

Algorithm

The algorithm is illustrated below:

1. XOR all the elements presented in the array. Let the result be x.
2. XOR all numbers from 1 to n. Let the result be y.
3. XORing x & y gives the missing number.

C Implementation: Program to find the missing number

#include <stdio.h>
#include <stdlib.h>

int missingNo(int* a, int n)
{
    int x = 0, y = 0;

    for (int i = 0; i < n - 1; i++) {
        //xoring all elements
        x ^= a[i];
    }
    for (int i = 1; i <= n; i++) {
        //xoring 1 to n
        y ^= i;
    }

    //xoring x & y outputs missing number
    return x ^ y;
}

int main()
{
    int n, x, count = 0;

    printf("enter your range\n");
    scanf("%d", &n);

    printf("enter elements leaving one nummber in the range 1 to n\n");

    // dynamic array created for n-1 elements
    int* a = (int*)(malloc(sizeof(int) * (n - 1)));
    for (int i = 0; i < n - 1; i++) {
        scanf("%d", &a[i]);
    }
    // function to check duplicate exists or not
    printf("\nthe missing number is %d\n", missingNo(a, n));

    return 0;
}

Output

enter your range
5
enter elements leaving one nummber in the range 1 to n
2
4
3
5

the missing number is 1

Time and Space Complexity

• Time complexity: O(n) (for scanning the array)
• Space complexity: O(1)