# 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 <bits/stdc++.h>`

`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 <bits/stdc++.h>`

`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<<getMissingNo(arr,` `sizeof` `(arr)/` `sizeof` `(arr[0]));`

` ` `return` `0;`

`}`

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

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 <bits/stdc++.h>`

`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 mising Number`

`#include<bits/stdc++.h>`

`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;`

`}`

Output:

3

Time Complexity: O(n)

Auxiliary Space: O(1)