×

Algorithms Tutorial

Searching Algorithms

Dynamic Programming

Graph Algorithms

Backtracking Algorithms

Recursion

Operating System Algorithms

Miscellaneous Topics

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

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(n2) 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)

Related Tutorials

Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.