Question

Consider two sets of integers, X = [x1, x2, . . . , xn] and Y = [y1, y2, . . . , yn]. Write two versions of a FindUncommon(X, Y ) algorithm to find the uncommon elements in both sets.
Each of your algorithms should return an array with the uncommon elements, or an empty array if there are no uncommon elements.
You do not have to write the ‘standard’ algorithms – just use them. Therefore, you should be able to write each algorithm in about 10 lines of code. You must include appropriate
comments in your pseudocode.

(a) Write a pre-sorting based algorithm of FindUncommon(X, Y ). Your algorithm should strictly run in O(n log n).

(b) Write a Hashing based algorithm of FindUncommon(X, Y ). Your algorithm should run in O(n).

Answer 1

As no language is specified so I am writing the algorithm in c++

Pre-sorting based algorithm to findUncommon(X,Y) O(nlogn)

Imp Note/*

checking an array of values of X in array Y will not be enough there can be a case that elements present in array Y do not present in array X so we have to check for both

let’s consider a case

x = {1,2,4,5.7}

y = {2,5,8,1,9}

so we sort X and Y

x = {1,2,4,5,7}

y = {1,2,5,8,9}

values in X that are not in Y are

4,7

values in Y that are not in X are

8,9

so total uncommon elements are {4,7,8,9} ie count = 4;

*/

so i am provinding a code so that it would be easy to understand the problem

void uncommonNumbers(int X[],int Y[],int n){

Step :1 sort array X // sort(X,X+n); // sort array X

step:2-sort array Y // sort(Y,Y+n); // sort array y

step 3:traverse in array Y and find elements in arry X

// for(int i = 0;i<n;i++)

step 4: find the first index thst matches with Y[i] in array X

//auto index = lower_bound(X,X+n,Y[i])-X;

step 5 : if presenet then set it to -1

/*

if(X[index]==Y[i]){ // if value is X[index] matches with value in Y[i] then :

X[index] = -1; // if present then set its value to -1 because it should not participate for next number

}

*/

step 6:if not then print the number

// cout<<Y[i]<<" ";

step 7: repeat step 3,4,5 and 6 for array Y and find elements of array X

/* for(int i = 0;i<n;i++){

if(X[i]>0 and (binary_search(Y,Y+n,X[i]))){

// same as above only check X[i]!=-1

Y[i] = -1;

}

else if(X[i]>0){

cout<<X[i]<<" ";

}

}

}

*/

step 8: return 0;

Hashing Based Algorithm O(n)

step 1: start

step 2: declare a hashmap (map<int,int>ans)

step 3: traverse in array X and store the frequency in numbers in ans

/*

example X= [1,2,3,3]

ans[1] = 1;

ans[2] = 1;

ans[3] = 2; //frequency of numbers

*/

step 4: traverse in an array Y and check if it is present in map or not

step 5: Initialze i = 0 and traverse in array Y

step 6: if(ans.find(Y[i])==ans.end()) //it means that Y[i] does not present in array X

print Y[i] // so store that number

else

ans[Y[i]]-- //this is because there can be dublicate elements in the array

IMP note

/*

example

X = {1,2,2,,3}

Y = {2,2,2,3,4}

ans = {1:1, 2:2, 3:1} for array X

now for array Y when we are Traversing in it

2 occurs 3 times but in array X it occurs only 2 times so this can be a problem thats why we used ans[Y[i]]-- so that we can keep record of elements

*/

step : 7-Now traverse in map to find uncommon elements

/*

if map[i] >0 or map[i]<0 it means uncommon elements are there so print those numbers

for(auto it = res.begin();it!=res.end();it++){

if(it->second==0) // it->second is value in hash map if equal to zero then skip

continue;

else if(it->second<0){ // if less than zero it means peresent in Y but not in X

int i = it->second;

while(i<0){

cout<<it->first<<" "; // it->first is key in hashmap

// print key that are in Y but not in X

i++;

}

}

else{ // present in X but noy Present in Y

int i = it->second;

while(i>0){

cout<<it->first<<" "; // print key that are in X but not in Y

i--;

}

}

}

*/

step 9: return 0;

...............................................****************************.........................................................

code for finding uncommon numbers using sorting

#include <bits/stdc++.h>

using namespace std;

void uncommonNumbers(int X[],int Y[],int n){

sort(X,X+n);

sort(Y,Y+n);

for(int i = 0;i<n;i++){

auto index = lower_bound(X,X+n,Y[i])-X;

// find the first index if it matches with Y[i] in array X

if(X[index]==Y[i]){

X[index] = -1; // if present the set its value to -1 because it should not participate for next number

}

else{

cout<<Y[i]<<" ";

}

}

for(int i = 0;i<n;i++){

if(X[i]>0 and (binary_search(Y,Y+n,X[i]))){ // same as above only check X[i]!=-1

Y[i] = -1;

}

else if(X[i]>0){

cout<<X[i]<<" ";

}

}

}

int main()

{

int X[5] = {1,4,5,2,2};

int Y[5] = {2,2,2,2,3};

uncommonNumbers(X,Y,5);

return 0;

}

............................................********************************.....................................

code for finding uncommon number using hashing O(n)

#include <bits/stdc++.h>

using namespace std;

void uncommonNumbers(int X[],int Y[],int n){

map<int,int>res;

for(int i = 0;i<n;i++){

res[X[i]]++;

}

for(int i = 0;i<n;i++){

if(res.find(Y[i])==res.end()){

cout<<Y[i]<<" ";

}

else{

res[Y[i]]--;

}

}

for(auto it = res.begin();it!=res.end();it++){

if(it->second==0)

continue;

else if(it->second<0){

int i = it->second;

while(i<0){

cout<<it->first<<" ";

i++;

}

}

else{

int i = it->second;

while(i>0){

cout<<it->first<<" ";

i--;

}

}

}

}

int main()

{

int X[5] = {1,4,5,2,2};

int Y[5] = {2,2,2,2,3};

uncommonNumbers(X,Y,5);

return 0;

}

you can run them for better understanding

if any doubt, comment below