Count Pairs

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
3 upvotes
Asked in companies
OptumAmazonSprinklr

Problem statement

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)
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3 1 2 7
1 3 2 
2 1 1 2
1 2
Sample Output 1 :
2
0
Explanation Of Sample Input 1 :
For test 1:
For 'i' = 1, 'j' = 2, Value of the expression = 1 * 1 + 2 * 3 = 7.
For 'i' = 1, 'j' = 3, Value of the expression = 1 * 1 + 2 * 2 = 5.
For 'i' = 2, 'j' = 3, Value of the expression = 1 * 3 + 2 * 2 = 7.


For test 2:
For 'i' = 1, 'j' = 2, Value of the expression = 1 * 1 + 1 * 2 = 3.
Sample Input 2 :
2
7 1 3 124
13 4 82 40 14 27 37
9 5 6 203
13 19 7 23 23 19 28 18 18
Sample Output 2 :
3
7
Hint

How can you find the required sum for all possible pairs ?

Approaches (2)
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'.
Time Complexity

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

Space Complexity

O(1)
 

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

Code Solution
(100% EXP penalty)
Count Pairs
Full screen
Console