*819*

Question:-We are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in list. One of the integers is missing. Give an algorithm to find the missing integer.

Input:-1, 2, 4, 6, 3, 7, 8

Output:-5

We solved the same problem via sorting here. Another solution to the problem is possible that has a even smaller time complexity and requires just a single scan of the array.

The technique involved is:-

- Using the summation formula, get the sum of numbers till ‘n’

Σn = ((n) * (n+1))/2 - Sum all the elements of the array.
- Subtract the sum of the array from the total sum. This gives you the missing number

Here is an implementation of the same:-

//find missing number in array of size 'size' int findMissingNumberSummation(int arr[], int size) { int i; int sum = ((size) * (size+1))/2; int arr_sum = 0; //loop through the array and calculate array sum for(i = 0;i<size;i++) { arr_sum += arr[i]; } return (sum - arr_sum); }

*Time Complexity:-* O(n) for scanning the complete array

*Space Complexity:-* O(1)

**Method 4** (Using XOR operation)