# Find the Missing Number

## Find the Missing Number

You are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in the list. One of the integers is missing in the list. Write an efficient code to find the missing integer.
Example:

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

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

Method 1: This method uses the technique of the summation formula.

• Approach: The length of the array is n-1. So the sum of all n elements, i.e sum of numbers from 1 to n can be calculated using the formula n*(n+1)/2. Now find the sum of all the elements in the array and subtract it from the sum of first n natural numbers, it will be the value of the missing element.
• Algorithm:
1. Calculate the sum of first n natural numbers as sumtotal= n*(n+1)/2
2. Create a variable sum to store the sum of array elements.
3. Traverse the array from start to end.
4. Update the value of sum as sum = sum + array[i]
5. Print the missing number as sumtotal – sum
• Implementation:
 `#include ` `using` `namespace` `std;` `// Function to get the missing number` `int` `getMissingNo(``int` `a[], ``int` `n)` `{` `    ``int` `total = (n + 1) * (n + 2) / 2;` `    ``for` `(``int` `i = 0; i < n; i++)` `        ``total -= a[i];` `    ``return` `total;` `}` `// Driver Code` `int` `main()` `{` `    ``int` `arr[] = { 1, 2, 4, 5, 6 };` `    ``int` `n = ``sizeof``(arr) / ``sizeof``(arr[0]);` `    ``int` `miss = getMissingNo(arr, n);` `    ``cout << miss;` `}`

Output

`3`
• Complexity Analysis:
• Time Complexity: O(n).
Only one traversal of the array is needed.
• Space Complexity: O(1).
No extra space is needed

Modification for Overflow

• Approach: The approach remains the same but there can be overflow if n is large. In order to avoid integer overflow, pick one number from known numbers and subtract one number from given numbers. This way there won’t have Integer Overflow ever.
• Algorithm:
1. Create a variable sum = 1 which will store the missing number and a counter variable c = 2.
2. Traverse the array from start to end.
3. Update the value of sum as sum = sum – array[i] + c and update c as c++.
4. Print the missing number as a sum.

 `#include ` `using` `namespace` `std;` `// a represents the array` `// n : Number of elements in array a` `int` `getMissingNo(``int` `a[], ``int` `n)` `{` `    ``int` `i, total=1;` `    ` `    ``for` `( i = 2; i<= (n+1); i++)` `    ``{` `        ``total+=i;` `        ``total -= a[i-2];` `    ``}` `    ``return` `total;` `}` `//Driver Program` `int` `main() {` `    ``int` `arr[] = {1, 2, 3, 5};` `    ``cout<

Output:

`4`

• Complexity Analysis:
• Time Complexity: O(n).
Only one traversal of the array is needed.
• Space Complexity:O(1).
No extra space is needed

Thanks to Sahil Rally for suggesting this improvement.
Method 2: This method uses the technique of XOR to solve the problem.

• Approach:
XOR has certain properties
• Assume a1 ^ a2 ^ a3 ^ …^ an = a and a1 ^ a2 ^ a3 ^ …^ an-1 = b
• Then a ^ b = an
• Algorithm:
1. Create two variables a = 0 and b = 0
2. Run a loop from 1 to n with i as counter.
3. For every index update a as a = a ^ i
4. Now traverse the array from start to end.
5. For every index update b as b = b ^ array[i]
6. Print the missing number as a ^ b.
• Implementation:
 `#include ` `using` `namespace` `std;` `// Function to get the missing number` `int` `getMissingNo(``int` `a[], ``int` `n)` `{` `    ``// For xor of all the elements in array` `    ``int` `x1 = a[0];` `    ``// For xor of all the elements from 1 to n+1` `    ``int` `x2 = 1;` `    ``for` `(``int` `i = 1; i < n; i++)` `        ``x1 = x1 ^ a[i];` `    ``for` `(``int` `i = 2; i <= n + 1; i++)` `        ``x2 = x2 ^ i;` `    ``return` `(x1 ^ x2);` `}` `// Driver Code` `int` `main()` `{` `    ``int` `arr[] = { 1, 2, 4, 5, 6 };` `    ``int` `n = ``sizeof``(arr) / ``sizeof``(arr[0]);` `    ``int` `miss = getMissingNo(arr, n);` `    ``cout << miss;` `}`

Output:

`3`

• Complexity Analysis:
• Time Complexity: O(n).
Only one traversal of the array is needed.
• Space Complexity: O(1).
No extra space is needed.

Method 3: This method will work only in python.
Approach:
Take the sum of all elements in the array and subtract that from the sum of n+1 elements. For Eg:
If my elements are li=[1,2,4,5] then take the sum of all elements in li and subtract that from the sum of len(li)+1 elements. The following code shows the demonstration.

 `// C++ program to find` `// the missing Number` `#include` `using` `namespace` `std;` `// getMissingNo takes list` `// as argument` `int` `getMissingNo(``int` `a[] ,` `                 ``int` `n)` `{` `  ``int` `n_elements_sum = n * (n + 1) / 2 ;` `  ``int` `sum = 0;` `  ``for``(``int` `i = 0; i < n - 1; i++)` `    ``sum += a[i];` `  ``return` `n_elements_sum-sum;` `}` `// Driver code` `int` `main()` `{` `  ``int` `a[] = {1, 2, 4, 5, 6};` `  ``int` `n = ``sizeof``(a) /` `          ``sizeof``(a[0]) + 1;` `  ``int` `miss = getMissingNo(a, n);` `  ``cout << (miss);` `  ``return` `0;` `}` `// This code is contributed by Chitranayal`

Output:

`3`

Time Complexity: O(n)

Auxiliary Space: O(1)

Last Updated on October 16, 2021 by admin

## Count Inversions in an array (Using Merge Sort)Count Inversions in an array (Using Merge Sort)

Count Inversions in an array (Using Merge Sort) Inversion Count for an array indicates –

## Find subarray with given sumFind subarray with given sum

Find subarray with given sum Given an unsorted array of nonnegative integers, find a continuous

## Maximum and minimum of an array using minimum number of comparisonsMaximum and minimum of an array using minimum number of comparisons

Maximum and minimum of an array using minimum number of comparisons   Write a C

Linked List vs Array Arrays store elements in contiguous memory locations, resulting in easily calculable

## Given an array A[] and a number x, check for pair in A[] with sum as xGiven an array A[] and a number x, check for pair in A[] with sum as x

Given an array A[] and a number x, check for pair in A[] with sum

## Array of Strings in C++Array of Strings in C++

Array of Strings in C++ (All Different Ways to Create) In C and C++, a

## Print a given matrix in spiral formPrint a given matrix in spiral form

Print a given matrix in spiral form Given a 2D array, print it in spiral

## Stock Buy Sell to Maximize ProfitStock Buy Sell to Maximize Profit

Stock Buy Sell to Maximize Profit The cost of a stock on each day is