C++ Coding Test Course, Representing Sets

We will explore algorithm problems related to set representation commonly used in coding tests. Understanding various data structures and algorithms is essential for effectively representing and manipulating sets. In this article, we will present an algorithm problem that involves representing sets and performing operations, and we will solve it step by step.

Problem: Intersection of Two Sets

This problem involves finding the set of common elements from the two given sets of numbers. This is one of the basic set operations and can be easily solved using C++ STL.

Problem Definition


Input:
 - Two integers N, M (1 ≤ N, M ≤ 100,000): the number of elements in the first set N, the number of elements in the second set M
 - Elements of the first set: N integers a1, a2, ..., aN
 - Elements of the second set: M integers b1, b2, ..., bM

Output:
 - Print the elements of the intersection of the two sets in ascending order.

Example


Input:
5 4
1 2 3 4 5
3 4 5 6

Output:
3 4 5

Problem Solving Process

Step 1: Problem Analysis

To find the intersection of the two given sets, we need to compare the elements of the two sets to find the common elements. For this, we can use a hash set data structure, and C++ STL provides std::unordered_set that we can utilize.

Step 2: Algorithm Design

The algorithm can be designed as follows.

  1. Take input for the two sets.
  2. Store the elements of the first set in a hash set.
  3. Iterate through each element of the second set and check if it exists in the hash set of the first set.
  4. If it exists, add it to the list of intersection elements.
  5. Sort the results in ascending order and print them.

Step 3: C++ Code Implementation

Let’s write the C++ code based on the above algorithm.


#include <iostream>
#include <unordered_set>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N, M;
    cin >> N >> M;

    unordered_set setA;
    vector intersection;

    // Input first set
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        setA.insert(a);
    }

    // Input second set and find intersection
    for (int i = 0; i < M; i++) {
        int b;
        cin >> b;
        // If b exists in setA, add to intersection
        if (setA.find(b) != setA.end()) {
            intersection.push_back(b);
        }
    }

    // Sort intersection elements
    sort(intersection.begin(), intersection.end());

    // Print result
    for (int num : intersection) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Step 4: Code Explanation

This code performs the following tasks:

  • unordered_set setA;: Declares an unordered set to store the elements of the first set.
  • vector intersection;: Declares a vector to store the intersection elements.
  • Receives input for the elements of the first set and adds them to the hash set using setA.insert(a);.
  • Iterates through each element of the second set and checks if it exists in setA.find(b), and if it does, adds it to the intersection array.
  • Finally, sorts the results and prints them.

Step 5: Complexity Analysis

From a time complexity standpoint, the process of adding elements of the first set to the hash set takes O(N), and the process of searching the hash set for each element of the second set takes O(M). Therefore, the overall time complexity of the algorithm is O(N + M). The memory complexity is O(N + min(N, M)), considering the memory used by the hash set and the intersection storage.

Summary and Conclusion

In this post, we explored the problem of representing sets and calculating their intersection. We were able to implement it easily using C++ STL, and we confirmed that the algorithm’s time complexity is efficient. To effectively solve set-related problems this way, it is essential to choose the right data structure.

For further learning, I recommend studying various practice problems and other operations on sets (such as union, difference, etc.). Thank you!