Q. Write an algorithm and program to find the missing number in array.

Find the Missing Number : This section focuses on missing number algorithm and program. This program should be practiced to improve the coding skills required for various interviews (campus interviews, walk-in interviews), coding rounds etc.

Given an integer array of length n and our task is to print the missing number in an array.
Array : An array is a collection of items stored at contiguous memory locations. For Example :-

Input : arr[] = {1, 2, 3, 4, 6, 7, 8}
Output : 5
Explanation : As we can see that input integer array is 1, 2, 3, 4, 6, 7, 8. Now, we need to see which number is missing, as we can see 5 number is missing. So, output for the following code is 5.

Now let us understand what logic we need to use in this :
1. Firstly, we need to find sum of all n elements, i.e sum of numbers from 1 to n can be calculated using the formula n*(n+1)/2.
2. Loop will run throughout the program. The loop will start from i = 0 to n-1.
3. Subtract the sum of all the elements by first n natural numbers, it will be the value of the missing element.

Algorithm To Find the Missing Number

\\Algorithm To Find the Missing Number
START
Step 1 : Calculate the sum of first n natural numbers as sumtotal= n*(n+1)/2
Step 2 : Create a variable sum to store the sum of array elements
Step 3 : Traverse the array from start to end.
Step 4 : Update the value of sum as sum = sum + array[i]
Step 5 : Print the missing number as sumtotal – sum
Stop

Program To Find the Missing Number

C++

Java

Python

PHP

//C Program To Find the Missing Number
#include <stdio.h> 
  
int main()
{
    int a[5] = { 1, 2, 4, 5, 6 }, n=5;
    int i, sum;
    sum = (n + 1) * (n + 2) / 2;
    for (i = 0; i < n; i++)
        sum -= a[i];
    printf("%d", sum);
    return 0;
}

//C++ Program To Find the Missing Number
#include <iostream>
using namespace std;

int main()
{
    int arr[] = { 1, 2, 4, 5, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int sum = (n + 1) * (n + 2) / 2;
    for (int i = 0; i < n; i++)
        sum -= arr[i];
    cout << sum;

}

//Java Program To Find the Missing Number

public class LFC
{
  public static void main(String[] args) {
    int arr[] = { 1, 2, 4, 5, 6 }, n=5;
    int i, sum;
        sum = (n + 1) * (n + 2) / 2;
        for (i = 0; i < n; i++)
            sum -= arr[i];
        System.out.println(sum);
  }
}

#Python Program To Find the Missing Number

arr = [1, 2, 4, 5, 6]
n = len(arr)
total = (n + 1)*(n + 2)/2
sum_of_arr = sum(arr)
rem= total - sum_of_arr
print(rem)

//C# Program To Find the Missing Number

using System;
class LFC {

    public static void Main()
    {
        int[] arr = { 1, 2, 4, 5, 6 }, n=5;
        int sum = (n + 1) * (n + 2) / 2;
        for (int i = 0; i < n; i++)
            sum -= arr[i];
        Console.Write(sum);
    }
}

<?php
//PHP Program To Find the Missing Number

$arr = array(1, 2, 4, 5, 6);
$n=5;
$sum = ($n + 1) * ($n + 2) / 2; 
for ( $i = 0; $i < $n; $i++)
    $sum -= $arr[$i];
echo($sum);

//C Program To Find the Missing Number
#include <stdio.h> 
  
int main()
{
    int a[5] = { 1, 2, 4, 5, 6 }, n=5;
    int i, sum;
    sum = (n + 1) * (n + 2) / 2;
    for (i = 0; i < n; i++)
        sum -= a[i];
    printf("%d", sum);
    return 0;
}

Output

Missing Number In Array : 3

Recommended Programs

Program to find sum of array elements.
Program to find pairs with given sum in an array.