Question

Consider two sets of integers represented in arrays, X = [x1, x2, . . . , xn] and Y =
[y1, y2, . . . , yn]. Write two versions of a FindSetUnion(X, Y ) algorithm to find the union of X
and Y as an array. An element is in the union of X and Y if it appears in at least one of X and Y .
You may make use any algorithm introduced in the lectures to help you develop your solution. That
is, 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.

question:

(a) [2 Marks] Write a pre-sorting based algorithm of FindSetUnion(X, Y ). Your algorithm
should strictly run in O(n log n).
(b) [2 Marks] Write a Hashing based algorithm of FindSetUnion(X, Y ). Your algorithm should
run in O(n).

Answer 1

Answer :

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

I hope this answer is helpful to you, please upvote my answer. I'm in need of it.. Thank you..