Home Arrays Find the missing number in an array.

Find the missing number in an array.

by nikoo28
2 comments 3 minutes read

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.

You may also like

2 comments

Ankur September 20, 2015 - 14:17

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

nikoo28 September 21, 2015 - 13:15

Hi Ankur,

Thanks for pointing it out. Have corrected the typo.

Comments are closed.

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