Symmetric 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 Symmetric Difference operation on the sets.
Theory
The Symmetric Difference of two sets A and B is represented as:
A △ B
It contains all elements which belong to either Set A or Set B but not to both sets. Mathematically,
A △ B = (A − B) ∪ (B − A)
It can also be represented as:
A △ B = (A ∪ B) − (A ∩ B)
Example
Consider the following two sets:
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
The common elements are 3 and 4. Therefore, these elements are excluded from the Symmetric Difference.
A − B = {1, 2}
B − A = {5, 6}
Therefore:
A △ B = {1, 2, 5, 6}
Alternative Definition
The Symmetric Difference can also be calculated using Union and Intersection:
A △ B = (A ∪ B) − (A ∩ B)
That means:
- Find the Union of A and B.
- Find the Intersection of A and B.
- Remove the common elements from the Union.
- The remaining elements form the Symmetric Difference.
Algorithm
- Start.
- Read the elements of Set A.
- Read the elements of Set B.
- Take each element of Set A.
- Check whether the element is present in Set B.
- If it is not present in Set B, add it to the result.
- Take each element of Set B.
- Check whether the element is present in Set A.
- If it is not present in Set A, add it to the result.
- Display the Symmetric Difference Set.
- Stop.
Flowchart
Example Table
| Operation | Result |
|---|---|
| Set A | {1, 2, 3, 4} |
| Set B | {3, 4, 5, 6} |
| A − B | {1, 2} |
| B − A | {5, 6} |
| A △ B | {1, 2, 5, 6} |
C Program
The following C program finds the Symmetric Difference of two sets without using any built-in set functions.
/* C Program to find Symmetric Difference of Two Sets */
#include <stdio.h>
int main()
{
int A[100], B[100], result[200];
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
Elements present in A but not in 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)
{
result[k] = A[i];
k++;
}
}
/*
Find B - A
Elements present in B but not in A
*/
for(i = 0; i < m; i++)
{
found = 0;
for(j = 0; j < n; j++)
{
if(B[i] == A[j])
{
found = 1;
break;
}
}
if(found == 0)
{
result[k] = B[i];
k++;
}
}
printf("\nSymmetric Difference of A and B:\n");
if(k == 0)
{
printf("Empty Set");
}
else
{
for(i = 0; i < k; i++)
{
printf("%d ", result[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 Symmetric Difference of A and B: 1 2 5 6
How the C Program Works
- The program reads Set A and Set B.
- It first finds elements present in A but not in B.
- These elements represent A − B.
- It then finds elements present in B but not in A.
- These elements represent B − A.
- Both results are stored in the result array.
- The result array represents the Symmetric Difference.
C++ Program
The following C++ program performs the Symmetric Difference operation using vectors and comparison logic.
/* C++ Program to find Symmetric 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 << "\nSymmetric Difference of A and B:\n";
bool foundAny = false;
/*
Find A - B
*/
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;
}
}
/*
Find B - A
*/
for(int i = 0; i < m; i++)
{
bool found = false;
for(int j = 0; j < n; j++)
{
if(B[i] == A[j])
{
found = true;
break;
}
}
if(!found)
{
cout << B[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 Symmetric Difference of A and B: 1 2 5 6
Java Program
The following Java program finds the elements that belong to exactly one of the two sets.
/* Java Program to find Symmetric Difference of Two Sets */
import java.util.Scanner;
public class SetSymmetricDifference
{
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("\nSymmetric Difference of A and B:");
boolean foundAny = false;
/*
Find A - B
*/
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;
}
}
/*
Find B - A
*/
for(int i = 0; i < m; i++)
{
boolean found = false;
for(int j = 0; j < n; j++)
{
if(B[i] == A[j])
{
found = true;
break;
}
}
if(!found)
{
System.out.print(B[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 Symmetric Difference of A and B: 1 2 5 6
Python Program
Python provides a built-in set data type. The Symmetric Difference can be performed using the ^ operator.
# Python Program to find Symmetric Difference of Two Sets
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
print("Set A =", A)
print("Set B =", B)
result = A ^ B
print("Symmetric Difference =", result)
Sample Output (Python)
Set A = {1, 2, 3, 4}
Set B = {3, 4, 5, 6}
Symmetric Difference = {1, 2, 5, 6}
Python Using symmetric_difference() Method
Python also provides the symmetric_difference() method.
# Python Program using symmetric_difference() method
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
result = A.symmetric_difference(B)
print("Set A =", A)
print("Set B =", B)
print("Symmetric Difference =", result)
Python Without Using Built-in Symmetric Difference
The following program implements the operation manually using the concept of Set Difference.
# Symmetric Difference without using built-in functions
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
result = set()
# Find A - B
for element in A:
if element not in B:
result.add(element)
# Find B - A
for element in B:
if element not in A:
result.add(element)
print("Set A =", A)
print("Set B =", B)
print("Symmetric Difference =", result)
Symmetric Difference using Union and Intersection
The Symmetric Difference can also be calculated using the formula:
A △ B = (A ∪ B) − (A ∩ B)
# Symmetric Difference using Union and Intersection
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
union = A | B
intersection = A & B
result = union - intersection
print("Union =", union)
print("Intersection =", intersection)
print("Symmetric Difference =", result)
Dry Run
Consider:
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
First we find A − B.
| Step | Element | Present in 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} |
A − B = {1,2}
Finding B − A
| Step | Element | Present in 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}
Final Symmetric Difference
The two difference sets are:
A − B = {1,2}
B − A = {5,6}
Therefore:
A △ B = {1,2,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) |
The nested loops compare elements of one set with elements of the other set. Therefore, the basic array-based implementation has O(n × m) time complexity.
Space Complexity
The result can contain elements from both sets. Therefore, the additional space required for the result can be:
O(n + m)
Properties of Symmetric Difference
- Symmetric Difference contains elements belonging to exactly one set.
- Common elements are excluded.
- It is commutative.
- It is associative.
- A △ A = ∅.
- A △ ∅ = A.
- A △ B = B △ A.
Difference Between Set Difference and Symmetric Difference
| Operation | Meaning | Example |
|---|---|---|
| A − B | Elements in A but not in B | {1,2} |
| B − A | Elements in B but not in A | {5,6} |
| A △ B | Elements in either A or B but not both | {1,2,5,6} |
Applications
- Database Operations
- Data Comparison
- Data Analysis
- Finding Unique Records
- Database Synchronization
- Data Cleaning
- Information Retrieval
- Comparing User Groups
- Artificial Intelligence
- Machine Learning
Advantages
- Easy to understand and implement.
- Helps identify elements unique to either set.
- Useful for comparing two collections.
- Can be implemented in multiple programming languages.
- Python provides built-in support for the operation.
Disadvantages
- Simple array-based implementations require nested loops.
- Large sets may increase execution time.
- Additional memory may be required for storing the result.
Viva Questions
- What is Symmetric Difference?
- What symbol is used for Symmetric Difference?
- What is the formula for Symmetric Difference?
- What is A △ B?
- What is the difference between Difference and Symmetric Difference?
- Is Symmetric Difference commutative?
- What is A △ A?
- What is A △ ∅?
- How can Symmetric Difference be implemented in Python?
- What is the time complexity of the given algorithm?
Frequently Asked Interview Questions
-
What is Symmetric Difference?
It is the set of elements that belong to either of two sets but do not belong to both sets. -
How is Symmetric Difference represented mathematically?
A △ B = (A − B) ∪ (B − A) -
Is Symmetric Difference commutative?
Yes.
A △ B = B △ A -
What is the Symmetric Difference of two identical sets?
The result is an empty set.
A △ A = ∅ -
What is the difference between A − B and A △ B?
A − B contains only elements belonging to A but not B. A △ B contains elements unique to either A or B. -
How is Symmetric Difference performed in Python?
It can be performed using the ^ operator or the symmetric_difference() method.
Practice Questions
- Write a C program to find the Symmetric Difference of two sets.
- Write a C++ program to find the Symmetric Difference of two sets.
- Write a Java program to find the Symmetric Difference of two sets.
- Write a Python program to find the Symmetric Difference of two sets.
- Find the Symmetric Difference of {2,4,6} and {4,5,6,7}.
- Find A △ B where A = {1,2,3} and B = {3,4,5}.
- Implement Symmetric Difference without using built-in functions.
- Explain the relationship between Difference and Symmetric Difference.
- Prove that A △ B = B △ A.
- Find A △ A.
Key Takeaways
- Symmetric Difference contains elements belonging to exactly one set.
- Common elements are removed.
- It is represented by the symbol △.
- A △ B = (A − B) ∪ (B − A).
- A △ B = (A ∪ B) − (A ∩ B).
- Symmetric Difference is commutative.
- A △ A = ∅.
- A △ ∅ = A.
- Python provides the ^ operator for Symmetric Difference.
Summary
The Symmetric Difference operation finds the elements that belong to either of two sets but do not belong to both sets. 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, A △ B = {1,2,5,6}. The Symmetric Difference can also be calculated using the formula (A ∪ B) − (A ∩ B). In this experiment, the operation has been implemented using C, C++, Java and Python.