# UOJ Passport Checking : Hash Table Method

The Interpol database contains a list of N stolen passport numbers. We have another list of M passport numbers to check if they are stolen or not.

Input

• The first line of the input contains an integer N.
• The next N lines contains the list of N stolen passport numbers, one passport number per line.
• The next line of the input contains an integer M.
• The next M lines contains the list of M passport numbers, one passport number per line.

Output

Output the total number of stolen passports in the list of M passports.

Constraints

• Time Limit: 3s
• Memory Limit: 64MB
• 1≤N≤100,000
• 1≤M≤100,000
• Passport numbers are alphanumeric (combination of alphabetic and numeric characters) and are of length at most 15

Problem Source: UTP Online Judge

Let’s try solving this problem using hash table. Hash table is a data structure that can map keys to value.

For example, you have 9999 students’ ID with code from `0001` to `9999` and store it in an array, `A[]`. Everyday, teachers will scan their ID if they’re present and you will receive an array of student list, say Present, like `{3478,0034,3203,0120,...,2840,0001}`. If the principal wants you to print a list of students that are absent, your code would probably be:

Pseudocode

```for i from 0001 to 9999
if not i in Present
print i
```

This is simple and straightforward but the time complexity is not really good. First, you have to go through every element from `0001` to `9999`, $n$. Then, to check if the element is in the list Present, you have to go through every element in that list, $m$. So, your time complexity will be $O(nm)$.

For hash table, the idea is as below:

Pseudocode

```for i in Present
A[i] = 1

for i from 0001 to 9999
if A[i] = 0
print i

```

It may look longer than the previous code, but it is much more efficient. First, we go through $m$ steps to record student who is present with `1` in their corresponding index. Then, we scan through `A[]` to print out the index of students with data `0`, which means they are absent. This method results in time complexity of $O(n+m)$ only.

Now, get back to the actual problem: Passport Checking. We first look at the overall solution involving hash table (`unordered_map` in C++):

C++

```#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

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

unordered_map<string, int> stolen_map;

unordered_map<string, int>::hasher fn = stolen_map.hash_function();

for (int i=0; i<N; i++){
string stolen;
cin >> stolen;

stolen_map[stolen] = fn(stolen);
}

int M;
cin >> M;

int cnt = 0;
for (int i=0; i<M; i++){
string target;
cin >> target;

unordered_map<string, int>::const_iterator got = stolen_map.find(target);
if (got != stolen_map.end()) cnt++;
}

cout << cnt << endl;

return 0;
}
```

Line `3`:

```#include <unordered_map>;
```

This allows us to use functions in `unordered_map`.

Line `11`:

```unordered_map<string, int> stolen_map;
```

Create a hash table to map `string` (stolen passports) to `int`.

Line 13:

```unordered_map<string, int>::hasher fn = stolen_map.hash_function();
```

Create a hash function (the method), `fn`,to convert the `string` (stolen passports) to `int` and store it in `stolen_map`.

Line `19`:

```stolen_map[stolen] = fn(stolen);
```

The stolen passport, type `string`, is store with their value after entering the hash function `fn`.

Line `30`:

```unordered_map<string, int>::const_iterator got = stolen_map.find(target);
```

To call for the `target` value.

Line `31`:

```if (got != stolen_map.end())
```

If the `target` value is searched.