# Find the Missing Number  Difficulty Level Easy
Arista Networks Array

## Problem Statement  In finding the missing number from an array of 1 to N numbers we have given an array that contains N-1 numbers. One number is missing from an array of numbers from 1 to N. We have to find the missing number.

## Input Format  First-line containing an integer N.

Second-line containing N-1 integers.

## Output Format  In a single line print the missing number.

• 2<=N<=100000
• 1<=a[i]<=N

## Approach 1 for Find the Missing Number  We use the Simple Mathematics formula as shown in the 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.

### Implementation for Find the Missing Number

#### C++ Program

```#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
int n;
cin>>n;
int a[n-1];
for(int i=0;i<n-1;i++)
{
cin>>a[i];
}
// sum1 store the sum of 1 to N numbers which is N*(N+1)/2;
ll sum1=(n*(n+1))/2;
ll sum2=0;
for(int i=0;i<n-1;i++)
{
//sum of elements present in the array;
sum2+=a[i];
}
cout<<"Missing number is: "<<sum1-sum2<<endl;
return 0;
}```

#### Java Program

```import java.util.Scanner;

class sum
{
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int arr[] = new int[n-1];
for(int i=0;i<n-1;i++)
{
arr[i] = sr.nextInt();
}
// sum1 store the sum of 1 to N numbers which is N*(N+1)/2;
int sum1=(n*(n+1))/2;
int sum2=0;
for(int i=0;i<n-1;i++)
{
//sum of elements present in the array;
sum2+=arr[i];
}
System.out.println("Missing number is: "+(sum1-sum2));
}
}```
```7
1 2 3 4 5 7```
`Missing number is: 6`

### Complexity Analysis for Find the Missing Number

#### Time Complexity

O(N) where N is the given value in the first line of input. Here we iterate the given array for finding the sum of elements.

Rotate Array

#### Space Complexity

O(1) because we don’t use any auxiliary space here. Just use some variables to store the sum.

## Approach 2 for Find the Missing Number  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.

### Implementation for Find the Missing Number

#### C++ Program

```#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
int n;
cin>>n;
int a[n-1];
for(int i=0;i<n-1;i++)
{
cin>>a[i];
}
int X = 0,Y = 0;
for(int i=1;i<=n;i++)
{
//XOR of all elements from 1 to N
X^=i;
}
for(int i=0;i<n-1;i++)
{
//XOR of all elements in the array
Y^=a[i];
}
int missing_Num=X^Y;
cout<<"Missing number is: "<<missing_Num<<endl;
return 0;
}```

#### Java Program

```import java.util.Scanner;

class sum
{
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int arr[] = new int[n-1];
for(int i=0;i<n-1;i++)
{
arr[i] = sr.nextInt();
}
int X = 0,Y = 0;
for(int i=1;i<=n;i++)
{
//XOR of all elements from 1 to N
X^=i;
}
for(int i=0;i<n-1;i++)
{
//XOR of all elements in the array
Y^=arr[i];
}
int missing_Num=X^Y;
System.out.println("Missing number is: "+missing_Num);
}
}```
```9
1 2 3 4 6 7 8 9```
`Missing number is: 5`

### Complexity Analysis for Find the Missing Number

#### Time Complexity

O(N) where N is the given value in the first line of input. Here we iterate the given array for finding the sum of elements.

Find whether an array is subset of another array

#### Space Complexity

O(1) because we don’t use any auxiliary space here. Just use some variables to store the xor of values.

References 