Find the missing number in an array.

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

Brute Force Solution:- One simple solution to this is, for each number in 1 to n check whether that number is in the given array or not. Return the number that is not present.
Here is the code module for the same:-

#include

//find missing number in array of size
int findMissingNumber(int arr[], int size)
{
	int i,j,found = 0;

	//loop through integers 1 to n
	for(i = 1; i<=size; i++)
	{
		//consider the number not to be present
		found = 0;

		//check in array
		for(j=0; j<size; j++)
			if(arr[j] == i)
				//if present change the flag
				found = 1;

		//if the number was not found, it was missing
		if(found == 0)
			return i;
	}
}

//driver program to test above function
int main(void)
{
	int arr[7] = {1, 2, 4, 6, 3, 7, 8};

	printf("The missing number is = ",findMissingNumber(arr,7));

	return 0;
}

Time Complexity:- O(n²)
Space Complexity:- O(1)

Method 2 – Sorting the array.
Method 3 – Using array summation.
Method 4 – Using XOR operator.