Count Pairs
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'

Question

Count Pairs

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

Accepted Answer

Using HashMap or self balancing BST for fastest result.

Accepted Answer

Brute Force

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.
Return 'CNT'.

Space Complexity: O(1)Explanation:

O(1)

We have only used constant extra space. So, the Space Complexity is constant, i.e. O(1).

Time Complexity: O(n^2)Explanation:

O(N * N), where 'N' is the size of the array.

The total number of pairs are 'N' * ('N' - 1) / 2. So, the Time Complexity is O(N * N).

C++ (g++ 5.4)

/*
    Time complexity: O(N * N)
    Space complexity: O(1)

    where 'N' is the size of the array.
*/

int countPairs(vector &a, int n, int x, int y, int sum) {
    // Store the count of the pairs.
    int cnt = 0;

    // Loop through the first element.
    for(int i = 0; i < n - 1; ++i) {
        // Loop through the second element.
        for(int j = i + 1; j < n; ++j) {
            // Calculating the sum.
            int cur_sum = a[i] * x + a[j] * y;
            // Increment 'cnt' if current sum is equal to required sum. 
            if(cur_sum == sum) {
                cnt++;
            }
        }
    }

    // Return the count of pairs.
    return cnt;
}

Python (3.5)

'''

	Time complexity: O(N * N)

	Space complexity: O(1)



	where 'N' is the size of the array.

'''

from typing import *



def countPairs(a: List[int], n: int, x:  int, y: int, sum: int) -> int:

	# Store the count of the pairs.

	cnt = 0



	# Loop through the first element.

	for i in range(n):

		# Loop through the second element.

		for j in range(i + 1, n) :

			# Calculating the sum.

			cur_sum = a[i] * x + a[j] * y

			# Increment 'cnt' if current sum is equal to required sum. 

			if(cur_sum == sum) :

				cnt += 1

			

	# Return the count of pairs.

	return cnt

Java (SE 1.8)

/*

    Time complexity: O(N * N)

    Space complexity: O(1)



    where 'N' is the size of the array.

*/



public class Solution {



    static int countPairs(int a[], int n, int x, int y, int sum) {

        // Store the count of the pairs.

        int cnt = 0;



        // Loop through the first element.

        for(int i = 0; i < n - 1; ++i) {

            // Loop through the second element.

            for(int j = i + 1; j < n; ++j) {

                // Calculating the sum.

                int cur_sum = a[i] * x + a[j] * y;

                // Increment 'cnt' if current sum is equal to required sum.

                if(cur_sum == sum) {

                    cnt++;

                }

            }

        }



        // Return the count of pairs.

        return cnt;

    }

}

Accepted Answer

Optimal

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'.

Space Complexity: OtherExplanation:

O(MAX_VALUE), where 'MAX_VALUE' is the maximum value in array 'A'.

We have used a frequency array, 'FREQ', which is of size O(MAX_VALUE).

Time Complexity: OtherExplanation:

O(N + MAX_VALUE), where 'N' is the size of the array and 'MAX_VALUE' is the maximum value in array 'A'.

For every element in 'A', we are just doing constant-time operations. Also, we are creating a 'FREQ' array which will take O(MAX_VALUE). So, the total Time Complexity is O(N + MAX_VALUE).