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

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

by nikoo28
0 comment

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

0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More