Find the missing number in an array. (Method 2)

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