Beautiful Pairs HackerRank Solution

Beautiful Pairs HackerRank Solution
Source : https://www.hackerrank.com/challenges/beautiful-pairs

You are given two arrays, and , both containing 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 element in 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 , the number of elements in and .
The second line contains space-separated integers .
The third line contains space-separated integers .

Constraints

Output Format

Determine and print the maximum possible number of pairwise disjoint beautiful pairs.

Note: You must first change element in , and your choice of element must be optimal.

Sample Input 0

41 2 3 41 2 3 3

Sample Output 0

4

Explanation 0

You are given and .
The beautiful set is and maximum sized pairwise disjoint beautiful set is either or .
We can do better. We change the element of array from to . Now new B array is: and the pairwise disjoint beautiful set is . 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.

Sample Input 1

63 5 7 11 5 85 7 11 10 5 8

Sample Output 1

6

Source : https://www.hackerrank.com/challenges/beautiful-pairs

Solution

	// Karthikalapati.blogspot.com
	import java.util.Scanner;
	// For an element in A, if there's a matching element in B, this creates a "beautiful pair".
	// Each element can only be used once to create a beautiful pair.
	// Additionaly, We MUST change exactly 1 element in B. We attempt to change it to create
	// 1 more beautiful pair. In the special case where we already have the max number of
	// beautiful pairs, being forced to change it gives us 1 less beautiful pair.
	// Time Complexity: O(n)
	// Space Complexity: O(1)
	public class Solution {
	private static final int MAX_NUM = 1000; // max value of any number in array
	public static void main(String[] args) {
	Scanner scan = new Scanner(System.in);
	int N = scan.nextInt();
	int [] bucketA = new int[MAX_NUM + 1];
	for (int i = 0; i < N; i++) {
	bucketA[scan.nextInt()]++;
	}
	int beautifulPairs = 0;
	for (int i = 0; i < N; i++) {
	int num = scan.nextInt();
	if (bucketA[num] > 0) {
	bucketA[num]--;
	beautifulPairs++;
	}
	}
	scan.close();
	/* Accounts for changing 1 element in B */
	if (beautifulPairs == N) {
	beautifulPairs--;
	} else {
	beautifulPairs++;
	}
	System.out.println(beautifulPairs);
	}
	}