Beautiful Pairs

You are given two arrays,  and B, both containing N integers.

A pair of indices  is beautiful if the  element of array  is equal to the  element of array . In other words, pair  is beautiful if and only if . A set containing beautiful pairs is called a beautiful set.

A beautiful set is called pairwise disjoint if for every pair  belonging to the set there is no repetition of either  or  values. For instance, if  and  the beautiful set  is not pairwise disjoint as there is a repetition of , that is .

Your task is to change exactly the element in B so that the size of the pairwise disjoint beautiful set is maximum.

Example:

Input: n = 6, A = {3, 5, 7, 11, 5, 8}, B = {5, 7, 11, 10, 5, 8}
Output: 6

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int beautifulPairs(vector<int> A, vector<int> B)
{
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    int N = A.size();
    int count = 0;
    for (int i = 0, j = 0; i < N && j < N; i++, j++)
    {
        while (j < N && A[i] != B[j])
        {
            if (A[i] > B[j])
                j++;
            while (i < N && A[i] < B[j])
                i++;
        }
        if (A[i] == B[j])
            count++;
    }
    if (count < N)
        return count + 1;
    else
        return count - 1;
}

int main()
{

    int n = 6;
    vector<int> A = {3, 5, 7, 11, 5, 8};
    vector<int> B = {5, 7, 11, 10, 5, 8};

    cout << beautifulPairs(A, B) << "\n";

    return 0;
}