Author: Konstantsin Sokol
Tester: Gedi Zheng
Editorialist: Miguel Oliveira
Given 2 sets of integers, count the number of integers that appear in both sets and the number of integers between 1 and N that do not appear in either set.
The source files that are both tracked and ignored are the intersection of the two sets given in the input.
The source files that are both untracked and unignored are the numbers in the interval [1, N] that do not appear in either of the given lists.
We are given 2 lists of unique integers. We can treat these lists as sets. A set is a collection of distinct items (integers in this case).
Both ignored and tracked source files
The source files that are both tracked and ignored are the integers in the intersection of the 2 given sets.
To calculate the set intersection, the simplest way is to search all integers of the first set in the second set. Since we have only 100 numbers, we could do this search naively with 2 nested loops and a time complexity of O(M*K).
A smarter way is to use a hash table. Note that the numbers are between 1 and 100. We can use an array with 100 positions and mark position i if number i is in the set. This way we can look-up if a number is in a set in O(1) time. Thus, the time complexity of the set intersection is O(M) to build set A, O(K) to build set B and O(M) to check if the items in set A appear in set B. The total time complexity of this set intersection is O(M+K).
Also, you can use set, map, unordered_map in C++ to make a look up table too.
Also, sometimes you can use bitwise operations with bit packing the sets in the integer to int or long data type. Then, you can use bitwise operations (e.g. and, or, xor) to check set intersection. Also, for two sorted arrays a, b, you can use set_intersection in C++ to find number of common elements in both the arrays in linear time.
Both unignored and untracked source files
The number of source files that are both untracked and unignored are the integers between 1 and N that do not appear in set A or B. We can use the same logic and search all numbers between 1 and N in sets A and B. This will take O(N) time if we use hashing or O(N * (M+K)) with the naive search.
The total time complexities are O(N + M + K) using hashing and O(M * K + N * (M+K)). Both were perfectly fine as the size of the sets are up to 100.