*974*

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(n^{2})

*Space Complexity:-* O(1)

**Method 2** – Sorting the array.

**Method 3** – Using array summation.

**Method 4** – Using XOR operator.

## 2 comments

In second loop, If condition should be :

if(arr[j] == i)

Hi Ankur,

Thanks for pointing it out. Have corrected the typo.

Comments are closed.