Problem Statement 1:
You are given an array A with N integers. Find the total number of good pairs of integers in A.
A pair of integer is good if:
- 1 < = i <= N
- 1 <= j <= N
- a[i] * a[j] can be represented as the sum of 2 prime numbers X, Y such that X ^ Y is an even number. (X, Y can be equal, X ^ Y represents bitwise xor between X and Y)
Constraints:
1 <= N <= 10^5
1 <= a[i] <= 10^6
Sample TestCases:
Input:
1
4
Output:
1
Explanation:
Here we have a = [4] and only 1 pair which is {4, 4} and 4 * 4 can be written as sum of 2 primes 4 * 4 = 16 = 11 + 5, Hence the answer is 1.
Input:
1
1
Output:
0
Explanation:
Here only 1 pair is possible which is {1, 1} and 1 * 1 can not be written as the sum of 2 primes. Hence the answer is 0.
Input:
3
2 1 3
Output:
3
Explanation:
3 valid pairs are: {2, 2}, {2, 3}, {3, 2} as 2 * 2 = 4 = 2 + 2, 2 * 3 = 6 = 3 + 3
Problem Statement 2:
It is given that the beauty of one pair (student, teacher) is equal to the difference in absolute value between the index of the student and the index of the teacher. The beauty of all pairs is the sum of beauties of each pair.
Your task is to find a total number of ways to make N pairs (student, teacher) such that the beauty of these pairs is equal to K.
Constraints:
1 <= N <= 50
0 <= K <= N * N
Sample TestCases:
Input:
3
2
Output:
2
Explanation:
Teachers -> 1 2 3 Students -> 1 2 3. There are two possible pair groups: {(1, 2), (2, 1), (3, 3)} and {(1, 1), (2, 3), (3, 2)}
Input:
3
3
Output:
0
Explanation:
It can be seen that there are no possible groups of pairs.
Input:
50
2
Output:
49
It would be very helpful if some can share their approach to these problems. Thanks!!
