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[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

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.