In this post, we will solve HackerRank Beautiful Pairs Problem Solution.
You are given two arrays. A and B, both containing N integers.
A pair of indices (i, j) is beautiful if the ith element of array A is equal to the jth element of array B. In other words, pair (i, j) is beautiful if and only if A[i] = B[j]. A set containing beautiful pairs is called a beautiful set.
A beautiful set is called pairwise disjoint if for every pair ([i], [i]) belonging to the set there is no repetition of either [i] or [i] values. For instance, if A = [10, 11, 12, 5, 14] and B = [8, 9, 11, 11, 5] the beautiful set [(1, 2), (1, 3), (3, 4)] is not pairwise disjoint as there is a repetition of 1, that is 1[0][0] = [1][0].
Your task is to change exactly 1 element in B so that the size of the pairwise disjoint beautiful set is maximum.
Function Description
Complete the beautifulPairs function in the editor below. It should return an integer that represents the maximum number of pairwise disjoint beautiful pairs that can be formed.
beautifulPairs has the following parameters:
- A: an array of integers
- B: an array of integers
Input Format
The first line contains a single integer n, the number of elements in A and B.
The second line contains n space-separated integers A[i].
The third line contains n space-separated integers B[i].
Output Format
Determine and print the maximum possible number of pairwise disjoint beautiful pairs.
Note: You must first change 1 element in B, and your choice of element must be optimal.
Sample Input 0
4 1 2 3 4 1 2 3 3
Sample Output 0
4
Explanation 0
You are given A = [1, 2, 3, 4] and B = [1, 2, 3, 3].
The beautiful set is [(0, 0), (1, 1), (2, 2), (2, 3)] and maximum sized pairwise disjoint
beautiful set is either [(0, 0), (1, 1), (2, 2)] or [(0, 0), (1, 1), (2, 3)].
We can do better. We change the 3rd element of array B from 3 to 4. Now new B array is:
B= [1, 2, 4, 3] and the pairwise disjoint beautiful set is [(0,0), (1, 1), (2, 3), (3, 2)]. So,
the answer is 4.
Note that we could have also selected index 3 instead of index 2 but it would have yeilded the same result. Any other choice of index is not optimal.
Beautiful Pairs C Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int n;
scanf("%d",&n);
int a[n],b[n],ik[n],jk[n];
int count = 0,counti=0,countj=0;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
ik[i] = jk[i] = 0;
}
for(int i=0;i<n;i++)
scanf("%d",&b[i]);
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(ik[i] == 0)
{
if(jk[j] == 0)
{
if(a[i] == b[j])
{
ik[i] ++;
jk[j] ++;
count++;
}
}
}
else
j=n;
}
}
/* for(int i=0;i<n;i++)
{
printf("*%d ^%d \n",ik[i],jk[i]);
if(ik[i]!=0)
counti++;
if(jk[i]!=0)
countj++;
}*/
//count = (counti>countj)?countj:counti;
//printf("%d ",counti);
//printf("%d ",countj);
if(count==n)
count--;
else
count++;
printf("%d",count);
return 0;
}
Beautiful Pairs C++ Solution
#include<iostream>
#include<cstdlib>
using namespace std;
int main()
{
int n,a,b,c=5;
int ans=0;
cin>>n;
int ar1[n],ar2[n];
for(a=0;a<n;a++) cin>>ar1[a];
for(a=0;a<n;a++) cin>>ar2[a];
for(a=0;a<n;a++)
{
for(b=0;b<n;b++)
{
if(ar1[a]==ar2[b])
{
ans++; ar1[a]=-121;
ar2[b]=-121;
break;
}
}
}
for(a=0;a<n;a++)
{
if(ar1[a]!=-121){ b=1;break;}}
for(a=0;a<n;a++){
if(ar2[a]!=-121) {
c=1;
}
}
if(ans==1000||ans==1) {ans--; cout<<ans; return 0;}
if(c==b) {ans++;}
cout<<ans;
}
Beautiful Pairs C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
class Solution {
static void Main(String[] args) {
int n = Convert.ToInt32(Console.ReadLine());
int[] a = Array.ConvertAll(Console.ReadLine().Split(' '), Convert.ToInt32);
int[] b = Array.ConvertAll(Console.ReadLine().Split(' '), Convert.ToInt32);
Dictionary<int, int> aValueCounts = new Dictionary<int, int>();
Dictionary<int, int> bValueCounts = new Dictionary<int, int>();
foreach (int aval in a) {
if (!aValueCounts.ContainsKey(aval)) aValueCounts.Add(aval, 0);
aValueCounts[aval]++;
}
foreach (int bval in b) {
if (!bValueCounts.ContainsKey(bval)) bValueCounts.Add(bval, 0);
bValueCounts[bval]++;
}
// Give me the count.
int baseCount = 0;
foreach (int bval in b) {
if (aValueCounts.ContainsKey(bval)) {
baseCount++;
if (--aValueCounts[bval] == 0) aValueCounts.Remove(bval);
}
}
if (aValueCounts.Count > 0)
baseCount++;
else
baseCount--;
Console.WriteLine(baseCount);
}
}
Beautiful Pairs Java Solution
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int[] A = readArray(in, N);
int[] B = readArray(in, N);
Arrays.sort(A);
Arrays.sort(B);
int i = 0;
int j = 0;
int count = 0;
while (i < N && j < N) {
if (A[i] < B[j]) i++;
else if (A[i] > B[j]) j++;
else {
i++;
j++;
count++;
}
}
if (count < N) count++;
else count--;
System.out.println(count);
}
public static int[] readArray(Scanner in, int N) {
int[] ar = new int[N];
for (int i = 0; i < N; i++) {
ar[i] = in.nextInt();
}
return ar;
}
}
Beautiful Pairs JavaScript Solution
const _ = require('lodash');
function main([[n], arr1, arr2]) {
const freq1 = new Array(1001).fill(0);
arr1.forEach(x => freq1[x] += 1);
let pairs = 0;
arr2.forEach(x => {
if (freq1[x] > 0) {
pairs += 1;
freq1[x] -= 1;
}
});
return pairs < n ? pairs + 1 : pairs - 1;
}
process.stdin.setEncoding('ascii');
let _input = '';
process.stdin.on('readable', () => _input += process.stdin.read() || '');
process.stdin.on('end', () => console.log(main(_input.split('\n').map(line => line.split(' ').map(Number)))));
Beautiful Pairs Python Solution
n = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
i = 0
j = 0
count_bp = 0
while i < n and j < n:
if A[i] == B[j]:
count_bp += 1
i += 1
j += 1
else:
if A[i] < B[j]:
i += 1
else:
j += 1
if count_bp != n:
print(count_bp + 1)
else:
print(count_bp - 1)