Home Arrays Find the missing number in an array.

Find the missing number in an array.

by nikoo28
2 comments

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(n2)
Space Complexity:- O(1)

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

2 comments

You may also like

2 comments

Ankur September 20, 2015 - 14:17

In second loop, If condition should be :
if(arr[j] == i)

Reply
nikoo28 September 21, 2015 - 13:15

Hi Ankur,

Thanks for pointing it out. Have corrected the typo.

Reply

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