Intersection of Two Sets using C, C++, Java and Python

---

❮ Previous    Next ❯

---

---

Objective

To write a program in C, C++, Java and Python to create two sets and perform the Intersection operation on the sets.

---

Theory

The intersection of two sets A and B is represented as:

A ∩ B

It contains only those elements which are present in both Set A and Set B. Mathematically,

A ∩ B = { x | x ∈ A and x ∈ B }

---

Important Points

• Intersection contains only common elements.
• An element must be present in both sets.
• Duplicate elements are not considered in a mathematical set.
• If there are no common elements, the intersection is an empty set.
• The intersection operation is represented by the symbol ∩.

---

Algorithm

1. Start.
2. Read the elements of Set A.
3. Read the elements of Set B.
4. Take each element of Set A one by one.
5. Check whether the element is present in Set B.
6. If the element is present in both sets, add it to the Intersection Set.
7. Display the Intersection Set.
8. Stop.

---

Flowchart

---

Example

Set	Elements
Set A	1, 2, 3, 4
Set B	3, 4, 5, 6
Intersection	3, 4

---

C Program

The following C program creates two sets and finds the common elements between them.

/* C Program to find Intersection of Two Sets */

#include <stdio.h>

int main()
{
    int A[100], B[100], intersection[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 Intersection */

    for(i = 0; i < n; i++)
    {
        found = 0;

        for(j = 0; j < m; j++)
        {
            if(A[i] == B[j])
            {
                found = 1;
                break;
            }
        }

        if(found == 1)
        {
            intersection[k] = A[i];
            k++;
        }
    }

    printf("\nIntersection of Set A and Set B:\n");

    if(k == 0)
    {
        printf("Empty Set");
    }
    else
    {
        for(i = 0; i < k; i++)
        {
            printf("%d ", intersection[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

Intersection of Set A and Set B:
3 4

---

How the C Program Works

1. Two arrays are used to store Set A and Set B.
2. The program reads the elements of both sets.
3. Each element of Set A is compared with every element of Set B.
4. If a match is found, the element is stored in the intersection array.
5. Finally, the common elements are displayed.

---

C++ Program

In C++, the intersection can be implemented using vectors. The following program uses arrays/vectors and does not depend on the built-in set intersection function.

/* C++ Program to find Intersection 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 << "\nIntersection of Set A and Set B:\n";

    bool foundAny = false;

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            if(A[i] == B[j])
            {
                cout << A[i] << " ";
                foundAny = true;
                break;
            }
        }
    }

    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

Intersection of Set A and Set B:
3 4

---

Java Program

The following Java program uses two arrays and compares their elements to find the common elements.

/* Java Program to find Intersection of Two Sets */

import java.util.Scanner;

public class SetIntersection
{
    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("\nIntersection of Set A and Set B:");

        boolean foundAny = false;

        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if(A[i] == B[j])
                {
                    System.out.print(A[i] + " ");
                    foundAny = true;
                    break;
                }
            }
        }

        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

Intersection of Set A and Set B:
3 4

---

Python Program

Python provides a built-in set data type. The intersection can be performed using the & operator or the intersection() method.

# Python Program to find Intersection of Two Sets

A = {1, 2, 3, 4}
B = {3, 4, 5, 6}

print("Set A =", A)
print("Set B =", B)

intersection = A & B

print("Intersection =", intersection)

---

Sample Output (Python)

Set A = {1, 2, 3, 4}

Set B = {3, 4, 5, 6}

Intersection = {3, 4}

---

Python Using intersection() Method

# Python Program using intersection() method

A = {1, 2, 3, 4}
B = {3, 4, 5, 6}

result = A.intersection(B)

print("Set A =", A)
print("Set B =", B)
print("Intersection =", result)

---

Python Without Using Built-in Intersection

The intersection operation can also be implemented manually. This helps students understand the actual logic behind the operation.

# Intersection 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 in B:

        result.add(element)

print("Set A =", A)
print("Set B =", B)
print("Intersection =", result)

---

Dry Run

Consider the following two sets:

A = {1, 2, 3, 4}

B = {3, 4, 5, 6}

Step	Element from Set A	Present in Set B?	Result
1	1	No	No change
2	2	No	No change
3	3	Yes	3 is added
4	4	Yes	4 is added

Final Intersection = {3, 4}

---

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 is the number of elements in Set A and m is the number of elements in Set B.

In Python, using the built-in set data structure can provide much better average-case performance because set membership is implemented using hashing.

---

Space Complexity

The additional space required depends upon the implementation. For storing the resulting intersection, the space complexity can be considered approximately:

O(min(n, m))

---

Applications

• Database Operations
• Data Analysis
• Search Engines
• Information Retrieval
• Data Filtering
• Artificial Intelligence
• Machine Learning
• Finding Common Records
• Comparing Two Data Collections

---

Advantages

• Easy to understand and implement.
• Helps identify common elements.
• Useful in data comparison.
• Widely used in database and information retrieval systems.
• Can be implemented in different programming languages.

---

Disadvantages

• Simple array-based implementation may require nested loops.
• Time complexity can become high for very large sets.
• Additional memory may be required to store the result.

---

Viva Questions

1. What is a Set?
2. What is the Intersection of two sets?
3. What symbol is used to represent Intersection?
4. What are common elements?
5. What is an empty set?
6. Can the intersection contain an element that exists in only one set?
7. What is the time complexity of the array-based intersection algorithm?
8. How is Intersection different from Union?
9. How can Intersection be performed in Python?
10. What is the use of the & operator in Python sets?

---

Frequently Asked Interview Questions

1. What is the difference between Union and Intersection?
   Union contains all unique elements from both sets, whereas Intersection contains only the elements common to both sets.


2. What happens if two sets have no common elements?
   The result is an empty set.


3. How is Intersection represented mathematically?
   It is represented by the symbol ∩.


4. How do you perform Intersection in Python?
   Python provides the & operator and the intersection() method.


5. Why are nested loops used in the C program?
   One loop selects an element from the first set and the second loop checks whether that element exists in the second set.

---

Practice Questions

1. Write a C program to find the Intersection of two sets.
2. Write a C++ program to find the Intersection of two sets.
3. Write a Java program to find the Intersection of two sets.
4. Write a Python program to find the Intersection of two sets.
5. Find the Intersection of {2, 4, 6, 8} and {4, 6, 10, 12}.
6. Find the Intersection of {1, 3, 5} and {2, 4, 6}.
7. Implement Intersection without using built-in set functions.
8. Compare Union and Intersection using a suitable example.

---

---

Summary

The Intersection operation is used to find the elements that are common to two sets. If Set A contains {1, 2, 3, 4} and Set B contains {3, 4, 5, 6}, their intersection is {3, 4}. In this experiment, the Intersection operation has been implemented using C, C++, Java and Python. The array-based implementations use comparisons to identify common elements, while Python also provides built-in set operations.

---

---

---

❮ Previous    Next ❯

---

---