# Beautiful Pairs

See the original problem on HackerRank.

## Solutions

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++:

  1 2 3 4 5 6 7 8 9 10  int beautifulPairs(vector& A, vector& B) { sort(begin(A), end(A)); sort(begin(B), end(B)); vector inters; set_intersection(begin(A), end(A), begin(B), end(B), back_inserter(inters)); if (inters.size() == A.size()) return inters.size() - 1; return inters.size() + 1; } 

This solution costs $$O(N \cdot logN)$$ because of using sort.

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:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18  int beautifulPairs(const vector& A, const vector& B) { array freq{}; for (auto i : B) freq[i]++; auto cnt = 0; for (auto i : A) { if (freq[i]) { freq[i]--; cnt++; } } return cnt + (cnt == A.size() ? -1 : 1); } 

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 Counter:

  1 2 3 4 5 6 7 8 9 10 11  def beautifulPairs(A, B): ac = Counter(A) bc = Counter(B) pairs = 0 for val in ac: if val in bc: pairs += min(ac[val],bc[val]) if pairs == len(A): return pairs - 1 else: return pairs + 1 
We've worked on this challenge in these gyms: modena