Count Pairs

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

Problem statement

You are given a cartesian plane, having ‘N’ points in the form of the array ‘PointX’ and ‘PointY’ where ‘PointX[i]’ and ‘PointY[i]’ represent the ‘X’ coordinates and ‘Y’ coordinates of the i’th point, respectively. You have to find the number of pairs satisfying the following conditions:

1. The points in the pair are distinct.
2. Euclidean distance and the Manhattan distance between the points of the pair should be equal.

Note :

1. Pair (‘P’, ‘Q’) is the same as pair (‘Q’, ‘P’).
2. Euclidean distance is given by: (( ‘X2’ - ‘X1’) ^ 2 + (‘Y2’ - ‘Y1’) ^ 2) ^ 0.5.
3. Manhattan distance is given by: |’X2’ - ‘X1’| + |’Y2’ - ‘Y1’|, where points are (‘X1’, ‘Y1’) and (‘X2’, ‘Y2’).
For example : 
Let points be: (1, 2), (2, 3), (1, 3)
The Euclidean distance between points (1, 2) and (1, 3) is: 1
The Manhattan distance between points (1, 2) and (1, 3) is: 1
The Euclidean distance between points (2, 3) and (1, 3) is: 1
The Manhattan distance between points (2, 3) and (1, 3) is: 1
So the pairs can be: [(1, 2), (1, 3)] and [(2, 3), (1, 3)].
So the number of pairs is 2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer ‘T’, denoting the number of test cases.

The first line of each test case contains a single integer ‘N’, representing the number of points in the cartesian plane.

The second line of each test case contains ‘N’ space-separated integers, representing the point’s ‘X’ coordinates.

The third line of each test case contains ‘N’ space-separated integers, representing the point’s ‘Y’ coordinates.
Output Format : 
For each test case, print the number of pairs satisfying the given conditions.

Print output of each test case in a separate line.
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 10^5
-10^9 <= PointX[i], PointY[i] <= 10^9

Time Limit: 1 sec
Sample Input 1 :
2
2
1 7
1 5
3
1 2 1
2 3 3
Sample Output 1 :
0
2
Explanation For Sample Input 1 :
For test case 1: 
The Euclidean distance between points (1, 1) and (7, 5) is: 10
The Manhattan distance between points (1, 1) and (7, 5) is: 2
Both the distances are not the same, so the number of pairs is 0.

For test case 2: 
The Euclidean distance between points (1, 2) and (1, 3) is: 1
The Manhattan distance between points (1, 2) and (1, 3) is: 1
The Euclidean distance between points (2, 3) and (1, 3) is: 1
The Manhattan distance between points (2, 3) and (1, 3) is: 1
So the pairs can be: [(1, 2), (1, 3)] and [(2, 3), (1, 3)].
So the number of pairs is 2.
Sample Input 2 :
2
3 
1 1 3
1 3 3
2
1 1
2 3
Sample Output 2 :
2
1
Hint

Try to check conditions for each pair.

Approaches (2)
Brute-Force Approach

The basic idea is to find the count of pairs satisfying the given conditions. We find all the possible pairs and check for the conditions.

 

Here is the algorithm :
 

  1. Create a variable (say, ‘COUNT’) that will store the count of pairs.
  2. Run a loop from 0 to ‘N’ (say, iterator ‘i’)
    • Run a loop from ‘i’ + 1 to ‘N’ (say, iterator ‘j’).
      • Check if the pairs satisfy the conditions by calling the CHECK function.
        • Increment ‘COUNT’ by 1.
  3. Finally, return ‘COUNT’.

 

CHECK(‘X1’, ‘Y1’, ‘X2’, ‘Y2’) 

 

  1. Check if ‘X1’ is equal to ‘X2’ and ‘Y1’ is equal to ‘Y2’
    • Return FALSE.
  2. Find the manhattan distance store it in a variable (say, ‘MANHATTAN’).
  3. Find the euclidean distance store it in a variable (say, ‘EUCLIDEAN’).
  4. Check if both are the same
    • Return TRUE
  5. Else, return FALSE.
Time Complexity

O(N^2), where ‘N’ is the number of points.

 

We iterate the ‘PointX’ and ‘PointY’ array once to traverse the coordinates and then run a nested loop to find the pairs. Therefore, the overall time complexity will be O(N^2).

Space Complexity

O(1)

 

We are not using any extra space. Therefore, the overall space complexity will be O(1).

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