See the original problem on HackerRank.
For each element in \(A\), we have to find the same element in \(B\). This is basically like performing the intersection between \(A\) and \(B\).
Then, since we have to change one element in \(B\) in any case:
- if the intersection is just \(A\), we return
A.size() - 1
- otherwise, we return
inters.size() + 1
Here is the idea in C++:
This solution costs \(O(N \cdot logN)\) because of using
Since the domain is small we can either use a better sorting strategy (e.g. radix, counting sort) or we can just use a frequency table:
This solution is linear time and constant space. Consider the tradeoff: if the domain changes we might be forced to change the solution.
In Python we can simply use