## 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
• C++
• Java
• Python
• C#
• PHP
• ```//C Program To Find the Missing Number
#include <stdio.h>

int main()
{
int a = { 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);
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 = { 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.