Last Updated: 23 Jan, 2022
Count Pairs
Moderate
Asked in companies
You are given an array 'A' of length 'N' consisting only of integers. You are also given three integers 'X', 'Y' and 'SUM'. Count the number of pairs ('i', 'j') where 'i' < 'j' such that ('A[i]' * 'X' + 'A[j]' * 'Y') = 'SUM'.
Example :
'N' = 3, 'A' = {3, 1, 2, 3}, 'X' = 4, 'Y'= 2, 'SUM' = 14
For 'i' = 1, 'j' = 2, Value of the expression = 4 * 3 + 2 * 1 = 14.
For 'i' = 1, 'j' = 3, Value of the expression = 4 * 3 + 2 * 2 = 16.
For 'i' = 1, 'j' = 4, Value of the expression = 4 * 3 + 2 * 3 = 18.
For 'i' = 2, 'j' = 3, Value of the expression = 4 * 1 + 2 * 2 = 8.
For 'i' = 2, 'j' = 4, Value of the expression = 4 * 1 + 2 * 3 = 10.
For 'i' = 3, 'j' = 4, Value of the expression = 4 * 2 + 2 * 3 = 14.
The possible pairs are :
(1, 3), (3,4)
Input Format :
The first line contains an integer 'T', which denotes the number of test cases to be run. Then the test cases follow.
The first line of each test case contains four integers 'N', 'X', 'Y', 'SUM' denoting the size of the array, coefficient of the first element, coefficient of the second element, and the sum to be searched for.
The next line contains 'N' space-separated integers representing the elements of the array.
Output format :
For each test case, print an integer, which denotes the number of pairs ('i', 'j') such that ('A[i]*X' + 'A[j]*Y') = 'SUM'.
Print the output of each test case in a new line.
Note :
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N <= 10^5
1 <= X, Y <= 10^4
1 <= SUM <= 10^9
0 <= A[i] <= 10^5
It is guaranteed that the count of pairs will fit in a 32-bit integer.
The Sum of 'N' over all test cases is <= 10^5.
Time Limit: 1 sec
Approaches
Approach :
- We can use two nested loops for all possible pairs. For every 'A[i]', we will use 'A[j]' such that 'i' < 'j' and calculate ('A[i]*X' + 'A[j]*Y').
- Be careful with the order as ('A[i]*X' + 'A[j]*Y') and ('A[j]*X' + 'A[i]*Y') are two different expressions for 'i' < 'j'.
Algorithm:
- Initialise an integer variable 'CNT' as 0.
- Loop through all the first elements from 'i' = 1 to 'i' = 'N' - 1 :
- Loop through all the second elements from 'j' = 'i' + 1 to 'j' = 'N' :
- Create a new variable 'CUR_SUM'.
- 'CUR_SUM' = 'A[i]' * 'X' + 'A[j]' * 'Y'.
- IF( 'CUR_SUM' == 'SUM') :
- 'CNT' = 'CNT' + 1.
- Loop through all the second elements from 'j' = 'i' + 1 to 'j' = 'N' :
- Return 'CNT'.
Approach :
- Let us write the given equation in another way, which is 'A[i]*X' = 'SUM' - 'A[j]*Y'.
- Suppose we know the value of 'A[j]', so we can calculate the value of RHS in the above equation.
- In the above equation, RHS is equal to 'A[i]*X', where both 'A[i]' and 'X' are integers. So RHS should be divisible by 'X'. If it is not, then there is no such pair for this RHS.
- Now, we will look for the number of elements in the array that are equal to ('SUM' - 'A[j]*Y') / 'X'. This can be easily calculated using a frequency array.
Algorithm:
- Initialise an integer variable 'CNT' as 0.
- Initialise an integer with the maximum value of 'A'.
- Create a frequency array 'FREQ' of length 'MAX_VALUE'.
- Loop through all the elements from 'j' = 1 to 'j' = 'N' :
- Create a new variable 'RHS'.
- 'RHS' = ('SUM' - 'A[j]' * 'Y').
- If 'RHS' is not divisible by 'X' or 'RHS' <= 0 :
- 'FREQ[ A[i] ]' = 'FREQ[ A[i] ]' + 1.
- Continue the loop.
- 'RHS' = 'RHS' / 'X'.
- Increment 'CNT' by 'FREQ[ RHS ]' if 'RHS' <= 'MAX_VALUE'.
- 'FREQ[ A[i] ]' = 'FREQ[ A[i] ]' + 1.
- Return 'CNT'.
Similar problems