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

# Find the missing number in an array. (Method 3)

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

We solved the same problem via sorting here. Another solution to the problem is possible that has a even smaller time complexity and requires just a single scan of the array.
The technique involved is:-

• Using the summation formula, get the sum of numbers till ‘n’
Σn = ((n) * (n+1))/2
• Sum all the elements of the array.
• Subtract the sum of the array from the total sum. This gives you the missing number

Here is an implementation of the same:-

//find missing number in array of size 'size'
int findMissingNumberSummation(int arr[], int size)
{
int i;

int sum = ((size) * (size+1))/2;

int arr_sum = 0;

//loop through the array and calculate array sum
for(i = 0;i<size;i++)
{
arr_sum += arr[i];
}

return (sum - arr_sum);
}


Time Complexity:- O(n) for scanning the complete array
Space Complexity:- O(1)

Method 4 (Using XOR operation)

#### You may also like

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