Home Arrays Find the missing number in an array.

# 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(found == 0)
return i;
}
}

//driver program to test above function
int main(void)
{
int arr = {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 September 20, 2015 - 14:17

In second loop, If condition should be :
if(arr[j] == i) September 21, 2015 - 13:15

Hi Ankur,

Thanks for pointing it out. Have corrected the typo.

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