Problem Solving: Union and Intersection of Sets

Learn to create a program that finds the union and intersection of two sets.

We'll cover the following

In this lesson, we’ll learn to compute the union and intersection of sets.

Instruction: Use the following playground to write the complete code for computing the union and intersection of sets.

We have already added code for loading, sorting, and displaying sets, so you do not need to include that.

Press + to interact
main.cpp
Sets.txt
/* The code for loading, sorting, and displaying sets has already 
been implemented, so we can now concentrate solely on calculating 
the union and intersection sets.*/
{
	/* 
	   Variables A, sizeA, B, sizeB have been declared 
		sets are available, and both are sorted now.
	*/
	int UnionSet[capacity] = { 0 }, uSize;
	
	// Write code here for computing UnionSet
	// Write code for displaying the UnionSet
	
	int IntersectionSet[capacity] = { 0 };
	
	// Write code here for computing IntersectionSet	
	
	// Write code for displaying the IntersectionSet	
}

Click the “Show Solution” button to see the complete solution.

Union of sets

Task: Compute the union of sets A and B, and display it on the console.

Let’s consider the following sets:

The program should print the union of sets A and B as follows:

A U B = {1, 2, 9, 7, 8, 10, 3, 4, 5}

The idea is the following:

  • First, we need to make a third set, UnionSet, in which we’ll initialize all numbers of the first set. This can easily be done by just copying set A to UnionSet.
  • For the second step, we’ll compare each element ebe_b of the second set with the first set elements. If the element ebe_b exists in A, then we will skip that element. Otherwise, simply add ebe_b into the UnionSet (i.e., placing it at the end of the array and increasing the size of the UnionSet set by 1).

Look at the following animation to understand the algorithm. The variable ui holds the intermediate size of the union set.

Understand the following code and then extend the playground with this UnionSet implementation.

Press + to interact
int UnionSet[capacity] = { 0 }, uSize;
for (int ai = 0; ai <= sizeA - 1; ai++)
{
	UnionSet[ai] = A[ai]; // Add all the elements in A in the unionSet
}
int ui = sizeA;
for (int bi = 0; bi <= sizeB - 1; bi++)
{
	bool found = false;  // FOR each value found should be reinitialized
	for (int ai = 0; (!found && ai <= sizeA-1); ai++)
	{
		if (B[bi] == A[ai]) // If any element of B exists in A then count and skip to add into third set
			found=true; 
	}
	if (!found) // if an element does not exist simply add into third set
	{
		UnionSet[ui] = B[bi];
		ui++;
	}
}
uSize = ui; // Size of union set store in uSize
  • Lines 2–5: We add all set A elements in UnionsSet in a loop.
  • Line 7–21: The variable ui holds the index in the union set. We check if the set B value is found in set A. If it is, we skip that value; otherwise, we add that value in UnionSet. The place UnionSet[ui] is the place where the new value will be added.

Note: Here we have used a flag found which is created just before the inner loop so that there is no need to reinitialize it before the next iteration.

  • Line 23: We store the size of the union set in uSize. We will use this size for sorting.

Exercise: Sort union-set

Task: Sort the union-set and print it.

The output should be the following:

A U B = {2, 3, 4, 5, 7, 8, 10}

Extend the playground and sort the union set that we have computed.

Intersection of sets

Task: Compute the intersection of A and B and display it on a console.

First, We should store this intersection in a third set and then print it. For example, for the sets A and B given above, the program should print:

A ∩ B = {2, 3, 4, 10}

The idea is the following:

  • For each element eae_a in the first set:
    • Search it in the second set.
    • If it’s there, add eae_a in the intersection set.

Understand the animation below.

Here is the code. Understand it and write it down in the above playground:

Press + to interact
int IntersectionSet[capacity] = { 0 };
int ii = 0, check = 0;
for (int ai = 0; ai <= sizeA - 1; ai++)
{
	for (int bi = 0; bi <= sizeB - 1; bi++)
	{
		if (B[bi] == A[ai])
		{
			check++; break;
		}	
	}
	if (check != 0)
	{
		IntersectionSet[ii] = A[ai];
		ii++;
	}
	check = 0;
}
//Displaying Intersection Set
int iSize = ii;
cout << "\nA ^ B = {";
for (int i = 0; i <= iSize-1; i++)
{
	cout << IntersectionSet[i];
	if (i != iSize-1)
		cout << ", ";
}
cout << "}";

Lines 3–18: We have to compare each element of set B with the set A. If any element of set B exists in set A, simply increment by 1 in the check variable and add that element into IntersectionSet. After each iteration, set the check variable to 0.

Lines 20–28: We have printed each element of IntersectionSet on a console.

Instruction: Add the above computing cross product code in the playground to complete the entire lesson.

Exercise: Improved implementation of union and intersection

The nested 2nd loop exhausts the entire second array in computing both union and intersection, if they’re not found. How can we improve the second loop?

Hint: Recall the sorted array.