Calculate Number of Elements that Belong in both Vectors in C++

Question

Our task is to calculate the number of elements that belong to both of the lists. For example, for the lists

vector<int> arr1{5,2,8,9}
vector<int> arr2{3,2,9,5}

The answer would 3 because the numbers 2, 5 and 9 belong to both of the lists. I want to make this algorithm in the least possible time complexity - O(nlogn). The goal is for me to sort the list and then iterate through both of them at once and find the common elements.

Here is what I have so far:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int counter;
    vector<int> arr1{ 5, 2, 8, 9 };
    vector<int> arr2{3, 2, 9, 5};

    sort(arr1.begin(), arr1.end()); // 2, 5, 8, 9
    sort(arr2.begin(), arr2.end()); // 2, 3, 5, 9

    for (int i = 0; i < 4; i++) {
        // insert code here
    }

    cout << counter;

    return 0;
}

Any help would be appreciated!

Answer 1

You can use std::set_intersection like:

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

int main() {
    std::vector<int> v1{ 1, 2, 3, 4, 5, 6, 7, 8 };
    std::vector<int> v2{ 5, 7, 9, 10 };
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());

    std::vector<int> v_intersection;

    std::set_intersection(
        v1.begin(), v1.end(),
        v2.begin(), v2.end(),
        std::back_inserter(v_intersection)
    );

    std::cout << v_intersection.size() << std::endl; // output: 2
}