# FIND 2 MISSING NUMBERS

The problem is to find 2 missing numbers between 1 and N.

For the purpose of simplicity N is considered as 10. Although with a bit modification the code would be generic.

**Input to this problem is 8 unique numbers between 1 and 10.
Output is 2 missing numbers.
**

**APPROACH 1:**

Consider all numbers between 1 and 10 and search for it in the array.

If not present in the array the number is missing.

Time complexity of this algorithm is O(N^N)

[sourcecode language=”C”]

#include<stdio.h>

#define MAX 10

int main(){

int n,i,j;

int arr[]={1,2,5,3,7,9,6,8};

printf("TWO MISSING NUMBERS ARE:");

for(i=1;i<=MAX;i++){

for(j=0;j<(MAX-2);j++){

if(arr[j]==i)

break;

}

if(j==MAX-2){

printf("%d ",i);

}

}

}

[/sourcecode]

**APPROACH 2:**

1.Create an array(count) of size 10 and initialize it to 0.

2.For each element in input array make count[element] = 1

This is shown in the above figure.

3.Loop through the count array and print the index whose array value is 0.

In the figure these indexes are highlighted.

**The time complexity of this algorithm is O(N)**

**But we need an extra array to store presence of a number.
Thus increasing the Space Complexity.
**

[sourcecode language=”C”]

#include<stdio.h>

#define MAX 10

int main(){

int n,i,j;

int arr[]={1,2,5,3,7,9,6,8};

int count[MAX]={};

printf("TWO MISSING NUMBERS ARE:");

for(i=0;i<MAX-2;i++){

count[arr[i]-1]=1;

}

for(i=0;i<MAX;i++){

if(count[i]==0)

printf("%d ",i+1);

}

}

[/sourcecode]

APPROACH 3:

1.Find the sum of 1st n terms using the formula : n*(n+1)/2 and store it in var s11.

2.Find the sum of square of 1st n terms using the formula : n*(n+1)*(2*n+1)/6 and store it in var s22.

3.Find sum of all numbers in input array(s1).

4.Find sum of square of all numbers in input array(s2).

Let the 2 missing numbers be x and y

Now we have:

x+y = s11 – s1

x^2 + y^2 = s22- s2

2 equations and 2 variables which can be solved simultaneously.

**Advantage of this algorithm is no extra space is required and also Time complexity is O(N).
**[sourcecode language=”C”]

#include<stdio.h>

#include<math.h>

#define MAX 10

int main(){

int n,i,s1=0,s2=0,s11,s22,miss1,miss2,temp1,temp2,d1,d2;

s11 = MAX*(MAX+1)/2;

s22 = MAX*(MAX+1)*(2*MAX + 1)/6;

int arr[]={1,2,5,3,7,9,6,8};

printf("TWO MISSING NUMBERS ARE:");

for(i=0;i<MAX-2;i++){

s1+=arr[i];

s2+=(arr[i]*arr[i]);

}

d1 = s11 – s1;

d2 = s22 – s2;

miss1 = (2*d1 + sqrt(4*d1*d1 – 8*(d1*d1 – d2)))/4;

miss2 = (2*d1 – sqrt(4*d1*d1 – 8*(d1*d1 – d2)))/4;

printf(" %d %d",miss1,miss2);

}

[/sourcecode]