*836*

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

After the brute force method we can also use another method to find the missing number in an array. This technique involves sorting the array. Sort the array and give it a linear scan, if there is a difference between index and the array element, that number is the missing number.

The algorithm can be written as:-

//find missing number in array of size int findMissingNumberSort(int arr[], int size) { int i; //sort the array quickSort(arr,size); //loop through integers 1 to size for(i = 0;i<size;i++) { //if the index does not match, return if((i+1) != arr[i]) return i; } }

*Time Complexity:-* O(nlog(n)) based on the sorting technique.

*Space Complexity:-* O(1)

**Method 3 (Better Time Complexity)** – Summation of array elements.

**Method 4 (Better Time Complexity)** – Using XOR operation