Problem Solving: Difference between Sets

Learn how to calculate the difference between sets.

We'll cover the following

In this lesson, we’ll compute the difference of two sets where the difference set A-B is the set of all elements that are in A but not in B. For example, if A = {1, 4, 7} and B = {7, 8}, then A-B = {1, 4}. In this case, element 7 is present in both A and B, so it is not included in A-B. So the resulting set only includes elements 1 and 4, which are unique to set A.

Instruction: Use the following playground to write the complete code for the task in this lesson.

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
// We have hidden deliberately the loading 
// and sorting and displaying part so that we can focus only
// on computing A-B and B-A sets.
{
	/* 
		Assume you have 
	    A, sizeA, B, sizeB 
		sets are available, and both are sorted now.
	*/
	
	// Write code here for computing A-B
	// Write code for displaying the AMinusB
	
	
	// Write code here for computing B-A
	// Write code for displaying the BMinusA
		
}

Difference between sets

Task: Compute the difference between the two sets A and B.

We want to print the set differences between A and B (both A-B and B-A). Again, first, we should store this difference in a third set and then print it. For example, for the sets A and B given above, the program should print:

Sample output:

A[] = {2 3 4 5 10}
B[] = {2 3 4 7 8 10}

A – B = {5}
B – A = {7,8}

The general idea is the following:

  • For every element ee of the first set, if we cannot find it in the second set, we will add that element to the difference set.

Look at the animation below to understand the algorithm:

Implementing A−BA - B

Let’s write down a code for both cases starting with A-B:

Press + to interact
// Case:1 A-B 
int AMinusB[500];
bool found;
int mi = 0;
for (int ai = 0; ai <= sizeA - 1; ai++)
{
    found = false;
    for (int bi = 0; bi <= sizeB - 1; bi++)
    {
        if (A[ai] == B[bi])
        {
            found = true; break;
        }
    }
    if (!found)
    {
        AMinusB[mi] = A[ai];
        mi++;
    }
}
// Print the case:1 A-B
int minusSize = mi;
cout << "\nA - B: = {";
for (int mi = 0; mi <= minusSize - 1; mi++)
{
cout << AMinusB[mi];
if (mi != minusSize - 1)
    cout << ", ";
}
cout << "}";

  • Lines 5–20: For every element of set A, we search it in set B. If it’s not found, we add that element into AminusB.

  • Line 22–30: We print the set AminusB on a console.

Exercise: Compute B-A

Write the code for computing B-A and print it.

Instruction: Add the above code in the playground and enable the program to compute the set differences for both A-B and B-A.