Problem: Missing Numbers

Sometimes you need to compare lists of number, but sorting each one normally will take too much time. Instead you can use alternative methods to find the differences between each list.

Challenge
Numeros The Artist was arranging two identical lists A and B into specific orders. The arrangements of the two arrays were random, Numeros was very proud of his arrangements. Unfortunately, some numbers got left out of List A. Can you find the missing numbers from A without messing up his order?

Details
There are many duplicates in the lists, but you need to find the extra numbers, i.e. B – A. Print the numbers in numerical order. Print each missing number once, even if it is missing multiple times. The numbers are all within a range of 100 from each other.

Input Format
There will be four lines of input:

n – the size of the first list
This is followed by n numbers that makes up the first list.
m – the size of the second list
This is followed by m numbers that makes up the second list.

Output Format
Output all the numbers (in ascending order) that are in B but not in A.

Constraints
1<= n,m <= 1000001
-10000 <= x <= 10000 , x ∈ B
Xmax – Xmin < 101

Sample Input

10
203 204 205 206 207 208 203 204 205 206
13
203 204 204 205 206 207 205 208 203 206 205 206 204

Sample Output

204 205 206

Explanation
Although 204 presented in both arrays, but 204’s frequency in A is smaller than that of B. Similarly 205 and 206 occur twice in A but thrice in B. So, these three numbers constitute the output. The rest of the numbers occur at least as many times in A as they do in B – so they are not “missing numbers”.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

struct Node{
int Value;
int Fre_A;
int Fre_B;
};

struct Node S[1000];

void QuickSort(int *a,long l,long r);
long Count(int *a,long n,int x);
void Delete_The_Same(int *a,long *n,int x);
void Process(int *a,int *b,long n,long m);

int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
long N,i;
scanf(“%ld”,&N);
int a[N];
for(i=0;i<N;++i)
scanf(“%d”,&a[i]);
long M,j;
scanf(“%ld”,&M);
int b[M];
for(j=0;j<M;++j)
scanf(“%d”,&b[j]);
QuickSort(a,0,N-1);
QuickSort(b,0,M-1);
Process(a,b,N,M);
return 0;
}

void QuickSort(int *a,long l,long r){
long i,j,x,temp;
x=a[(l+r)/2];
i=l; j=r;
do{
while(a[i]<x) i++;
while(a[j]>x) j–;
if(i<=j){
temp=a[i];
a[i]=a[j];
a[j]=temp;
i++; j–;
}
}while(i<j);
if(l<j)
QuickSort(a,l,j);
if(i<r)
QuickSort(a,i,r);
}

long Count(int *a,long n,int x){
long Count=0,i;
for(i=0;i<n;++i)
if(a[i]==x)
Count++;
return Count;
}

void Delete_The_Same(int *a,long &n,int x){
long Count=0,i,j;
for(i=0;i<n;++i)
if(a[i]==x)
Count++;
do{
for(i=0;i<n;++i){
if(a[i]==x){
for(j=i;j<n;++j)
a[j]=a[j+1];
n–;
Count–;
break;
}
}
}while(Count>0);
}

void Process(int *a,int *b,long n,long m){
long i=0,j;
do{
S[i].Value=a[0];
S[i].Fre_A=Count(a,n,a[0]);
S[i].Fre_B=Count(b,m,a[0]);
Delete_The_Same(a,n,a[0]);
i++;
}while(n>0);
for(j=0;j<i;++j){
if(S[j].Fre_B>S[j].Fre_A)
printf(“%d “,S[j].Value);
}
}

Advertisements