Common Elements

Difficulty: 1100 3500 ms 128 MB

implementation

Count the elements the two multisets share: for every value, min(count in A, count in B), summed.

Input: the first line has N; the second line has A's N values; the third line has B's N values.

Output: the multiset intersection size.

Constraints:

• 1 ≤ N ≤ 10⁵
• |values| ≤ 10⁹

Sample Tests

4
1 2 2 3
2 2 4 1

3

2
5 6
7 8

0

Read the Editorial