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!!
Can you please share problem links ?
These problems were asked in the coding round of a company some time ago. I don't have any links to these problems.
problem 1: may be it will help
The first problem seems easy:
First, notice that any even whole number up to 4 * 1e18 can be expressed as the sum of two prime numbers (experimentally proven), except 2. Second , notice, that in order for their XOR to be even, they should have the same last bit in their binary represntation.
After that we notice, that all numbers except 2 and 4 that are even are expressed as sum of two odd primes, as such it means that they both have 1 in their binary representation as the last bit, which means that their XOR is even.
As such, our problem is reduced to finding pairs of indexes i, j such that a[i] * a[j] is even and not equal to either 2 or 4. After that, the problem seems easy.
Thanks, I got it !!
But why it's wrong for 4 ? We can break 4 as 2 + 2 and 2 ^ 2 is even.
Missed that 2 ^ 2 is even(