Difference of Two Sets using C, C++, Java and Python
Objective
To write a program in C, C++, Java and Python to create two sets and perform the Difference operation on the sets.
Theory
The difference of two sets A and B is represented as:
A − B
It contains all those elements which belong to Set A but do not belong to Set B. Mathematically,
A − B = { x | x ∈ A and x ∉ B }
Difference of B − A
The Difference operation can also be performed in the reverse direction.
B − A = { x | x ∈ B and x ∉ A }
For the same example:
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
we get:
B − A = {5, 6}
Difference vs Intersection
| Operation | Meaning | Example |
|---|---|---|
| Intersection | Elements common to both sets | {3,4} |
| A − B | Elements in A but not in B | {1,2} |
| B − A | Elements in B but not in A | {5,6} |
Algorithm
- Start.
- Read the elements of Set A.
- Read the elements of Set B.
- Take each element of Set A one by one.
- Check whether the element is present in Set B.
- If the element is not present in Set B, add it to the Difference Set.
- Display the Difference Set A − B.
- Stop.
Flowchart
Example
| Set / Operation | Elements |
|---|---|
| Set A | {1, 2, 3, 4} |
| Set B | {3, 4, 5, 6} |
| A − B | {1, 2} |
| B − A | {5, 6} |
C Program
The following C program creates two sets and finds the elements which are present in Set A but not present in Set B.
/* C Program to find Difference of Two Sets */
#include <stdio.h>
int main()
{
int A[100], B[100], difference[100];
int n, m;
int i, j, k = 0;
int found;
printf("Enter number of elements in Set A: ");
scanf("%d", &n);
printf("Enter elements of Set A:\n");
for(i = 0; i < n; i++)
{
scanf("%d", &A[i]);
}
printf("Enter number of elements in Set B: ");
scanf("%d", &m);
printf("Enter elements of Set B:\n");
for(i = 0; i < m; i++)
{
scanf("%d", &B[i]);
}
/* Find A - B */
for(i = 0; i < n; i++)
{
found = 0;
for(j = 0; j < m; j++)
{
if(A[i] == B[j])
{
found = 1;
break;
}
}
if(found == 0)
{
difference[k] = A[i];
k++;
}
}
printf("\nDifference A - B:\n");
if(k == 0)
{
printf("Empty Set");
}
else
{
for(i = 0; i < k; i++)
{
printf("%d ", difference[i]);
}
}
return 0;
}
Sample Output (C)
Enter number of elements in Set A: 4 Enter elements of Set A: 1 2 3 4 Enter number of elements in Set B: 4 Enter elements of Set B: 3 4 5 6 Difference A - B: 1 2
How the C Program Works
- Two arrays are used to store Set A and Set B.
- The program reads the elements of both sets.
- Each element of Set A is compared with every element of Set B.
- If an element of Set A is not found in Set B, it is stored in the difference array.
- Finally, the elements of A − B are displayed.
C++ Program
The following C++ program performs the Difference operation without using the built-in set difference function.
/* C++ Program to find Difference of Two Sets */
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n, m;
cout << "Enter number of elements in Set A: ";
cin >> n;
vector<int> A(n);
cout << "Enter elements of Set A:\n";
for(int i = 0; i < n; i++)
{
cin >> A[i];
}
cout << "Enter number of elements in Set B: ";
cin >> m;
vector<int> B(m);
cout << "Enter elements of Set B:\n";
for(int i = 0; i < m; i++)
{
cin >> B[i];
}
cout << "\nDifference A - B:\n";
bool foundAny = false;
for(int i = 0; i < n; i++)
{
bool found = false;
for(int j = 0; j < m; j++)
{
if(A[i] == B[j])
{
found = true;
break;
}
}
if(!found)
{
cout << A[i] << " ";
foundAny = true;
}
}
if(!foundAny)
{
cout << "Empty Set";
}
return 0;
}
Sample Output (C++)
Enter number of elements in Set A: 4 Enter elements of Set A: 1 2 3 4 Enter number of elements in Set B: 4 Enter elements of Set B: 3 4 5 6 Difference A - B: 1 2
Java Program
The following Java program finds the elements that are present in Set A but not present in Set B.
/* Java Program to find Difference of Two Sets */
import java.util.Scanner;
public class SetDifference
{
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int n, m;
System.out.print("Enter number of elements in Set A: ");
n = sc.nextInt();
int[] A = new int[n];
System.out.println("Enter elements of Set A:");
for(int i = 0; i < n; i++)
{
A[i] = sc.nextInt();
}
System.out.print("Enter number of elements in Set B: ");
m = sc.nextInt();
int[] B = new int[m];
System.out.println("Enter elements of Set B:");
for(int i = 0; i < m; i++)
{
B[i] = sc.nextInt();
}
System.out.println("\nDifference A - B:");
boolean foundAny = false;
for(int i = 0; i < n; i++)
{
boolean found = false;
for(int j = 0; j < m; j++)
{
if(A[i] == B[j])
{
found = true;
break;
}
}
if(!found)
{
System.out.print(A[i] + " ");
foundAny = true;
}
}
if(!foundAny)
{
System.out.print("Empty Set");
}
sc.close();
}
}
Sample Output (Java)
Enter number of elements in Set A: 4 Enter elements of Set A: 1 2 3 4 Enter number of elements in Set B: 4 Enter elements of Set B: 3 4 5 6 Difference A - B: 1 2
Python Program
Python provides a built-in set data type. The Difference operation can be performed using the - operator.
# Python Program to find Difference of Two Sets
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
print("Set A =", A)
print("Set B =", B)
difference = A - B
print("Difference A - B =", difference)
Sample Output (Python)
Set A = {1, 2, 3, 4}
Set B = {3, 4, 5, 6}
Difference A - B = {1, 2}
Python Using difference() Method
The same operation can also be performed using Python's difference() method.
# Python Program using difference() method
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
result = A.difference(B)
print("Set A =", A)
print("Set B =", B)
print("Difference A - B =", result)
Python Without Using Built-in Difference
The following program implements the Difference operation manually. This is useful for understanding the actual algorithm.
# Difference of Two Sets without using built-in functions
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
result = set()
for element in A:
if element not in B:
result.add(element)
print("Set A =", A)
print("Set B =", B)
print("Difference A - B =", result)
Finding B − A in Python
# Difference B - A
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
result = B - A
print("B - A =", result)
Output: {5, 6}
Dry Run
Consider the following two sets:
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
We want to calculate:
A − B
| Step | Element from Set A | Present in Set B? | Action | Result |
|---|---|---|---|---|
| 1 | 1 | No | Add 1 | {1} |
| 2 | 2 | No | Add 2 | {1,2} |
| 3 | 3 | Yes | Skip 3 | {1,2} |
| 4 | 4 | Yes | Skip 4 | {1,2} |
Final Result: A − B = {1,2}
Dry Run for B − A
| Step | Element from Set B | Present in Set A? | Action | Result |
|---|---|---|---|---|
| 1 | 3 | Yes | Skip 3 | {} |
| 2 | 4 | Yes | Skip 4 | {} |
| 3 | 5 | No | Add 5 | {5} |
| 4 | 6 | No | Add 6 | {5,6} |
B − A = {5,6}
Time Complexity
| Implementation | Time Complexity |
|---|---|
| C | O(n × m) |
| C++ | O(n × m) |
| Java | O(n × m) |
| Python Manual Method | O(n × m) |
Here, n represents the number of elements in Set A and m represents the number of elements in Set B.
The nested-loop implementation checks each element of one set against the elements of the other set, resulting in O(n × m) time complexity.
Space Complexity
The result set can contain at most all elements of the first set. Therefore, the additional space required for the result is:
O(n)
Important Property of Set Difference
Applications
- Database Operations
- Data Filtering
- Comparing Data Sets
- Information Retrieval
- Finding Missing Records
- Data Cleaning
- Search Operations
- Artificial Intelligence
- Machine Learning
- Database Query Processing
Advantages
- Simple to understand and implement.
- Useful for finding unique elements of one set.
- Helps compare two collections of data.
- Useful in database and data analysis operations.
- Can be implemented in C, C++, Java and Python.
Disadvantages
- Array-based implementations require duplicate checking.
- Nested loops can become inefficient for very large sets.
- Additional memory may be required for storing the result.
- The result depends on the order of the sets.
Viva Questions
- What is a Set?
- What is the Difference of two sets?
- How is A − B defined?
- What symbol is used for Set Difference?
- What is the difference between A − B and B − A?
- Is Set Difference commutative?
- What happens when all elements of A are also present in B?
- What is the time complexity of the given algorithm?
- How can Difference be performed in Python?
- What is the difference between Difference and Intersection?
Frequently Asked Interview Questions
-
What is the difference between Union and Difference?
Union contains all unique elements from both sets, whereas Difference contains elements that belong to one set but not the other. -
What is the difference between Intersection and Difference?
Intersection finds common elements, whereas Difference finds elements that are present in one set but absent from the other. -
Is A − B equal to B − A?
No. Set Difference is not commutative. -
What is A − B if A = {1,2,3} and B = {2,3,4}?
A − B = {1} -
What is B − A for the same sets?
B − A = {4} -
How is Difference implemented in Python?
It can be performed using the - operator or the difference() method.
Practice Questions
- Write a C program to perform Difference of two sets.
- Write a C++ program to perform Difference of two sets.
- Write a Java program to perform Difference of two sets.
- Write a Python program to perform Difference of two sets.
- Find A − B where A = {2,4,6,8} and B = {4,6,10,12}.
- Find B − A for the above sets.
- Find A − B where A = {1,3,5,7} and B = {1,3,5,7}.
- Find the Difference of two sets without using built-in functions.
- Explain why Set Difference is not commutative.
- Differentiate Union, Intersection and Difference.
Key Takeaways
- Difference finds elements present in one set but not another.
- A − B contains elements present in A but absent from B.
- Difference is represented using the symbol −.
- Set Difference is not commutative.
- Generally, A − B is different from B − A.
- Difference can be implemented using C, C++, Java and Python.
- Python provides the - operator and difference() method.
Summary
The Difference operation is used to find the elements that are present in one set but not present in another set. For example, if A = {1,2,3,4} and B = {3,4,5,6}, then A − B = {1,2} and B − A = {5,6}. Therefore, the order of the sets is important while performing the Difference operation. In this experiment, the Difference operation has been implemented using C, C++, Java and Python.