# Find the missing number from Array of 1 to N numbers

0
380

## One number is missing from an array of numbers from 1 to N. Find the missing number.

### Method 1

TIME COMPLEXITY: O(N)

SPACE COMPLEXITY: O(1)

We use Simple Mathematics formula as shown in below algorithm

### Algorithm

1. We know the sum of numbers from 1 to N is given by the formula

N*(N+1)/2.

Let us call this as real_sum.

2. And then we sum the elements present in the array and let us call it missing_sum.

3. Simple the difference between real_sum and missing_sum is the missing number as it was not added while computing the missing_sum.

### Program for Method 1:

``````#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main()
{
int arr[] = {1,2,3,4,6,7,8,9};
int N = 9;

ll Sum =N*(N+1);
Sum = Sum>>1;  //if all numbers are present then the sum is N*(N+1)/2
ll sum = 0;
for(int i=0;i<sizeof(arr)/sizeof(arr[0]);i++)
sum += arr[i]; //sum of elements actually present in the array

cout <<"Missing number is "<<Sum-sum <<endl;

return 0;
}``````

### Method 2

TIME COMPLEXITY: O(N)

SPACE COMPLEXITY: O(1)

We use the concept of XOR operation.

As we know,

A xor A = 0   ————- Property 1

i.e. xor of 2 similar elements is zero.

Also,

A xor 0 = A   ————- Property 2

i.e. xor of any element with zero gives the same number.

### Algorithm

1. We compute the XOR of all the values from 1 to N and say it is X.

2. We compute the XOR of all the values in the array and say it is Y.

3. Now when we do (X xor Y) we basically are XORing all values twice except the missing number which came only once. Thus the final value is nothing but the missing number by property 2 of XOR.

Input: 1 2 3 4 6 7 8 9

output: 5

### Program for Method 2:

``````#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main()
{
int arr[] = {1,2,3,4,6,7,8,9};
int N = 9;

int X = 0,Y = 0;

for(int i=1;i<=N;i++)
X ^= i;	//XOR of all elements from 1 to N

for(int i=0;i<sizeof(arr)/sizeof(arr[0]);i++)
Y ^= arr[i]; //XOR of all elements in the array

int missing_Num = X^Y;
cout <<"Missing number is "<<missing_Num<<endl;

return 0;
}``````

If you have come this far, it means that you liked what you are reading. I am a software developer (graduated from BITS Pilani). I love writing technical articles on programming and data structures.