Last Updated: 9 Nov, 2021

Count Pairs

Moderate

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 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 :

Create a variable (say, ‘COUNT’) that will store the count of pairs.
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.
Finally, return ‘COUNT’.

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

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

Solve now

02 Approach

We have to find the pairs such that the Manhattan distance and Euclidean distance of the points in the pair are equal. Writing the condition in an equation, we get:

|’X2’ - ‘X1’| + |’Y2’ - ‘Y1’| = (( ‘X2’ - ‘X1’) ^ 2 + (‘Y2’ - ‘Y1’) ^ 2) ^ 0.5

Solving the above equation, we get ‘X1’ = ‘X2’ or ‘Y1’ = ‘Y2’. So we need to find the pairs satisfying either of the conditions.

We can use a map that stores the number of points having their ‘X’ coordinates equal to ‘X[i]’, a map for storing the number of points having their ‘Y’ coordinates equal to ‘Y[i]’, and another map to store the points equal to point (‘X[i]’, ‘Y[i]’).

The number of pairs will be: Number of pairs with same ‘X’ coordinates + Number of pairs with same ‘Y’ coordinates - Number of pairs with coincident points.

Here is the algorithm :

Create three maps (say, ‘mpX’, ‘mpY’, and ‘mpXY’) that will store the distinct ‘X’ coordinates, ‘Y’ coordinates, and distinct points.
Create a variable (say, ‘CountX’, ‘CountY’, and ‘CountXY’) that will store the count of ‘X’ coordinates, ‘Y’ coordinates, and distinct points and initialize them to 0.
Run a loop from 0 to ‘N’ (say, iterator ‘i’) to traverse the points.
- Check if ‘PointX[i]’ is already present in ‘mpX’
  - Update ‘CountX’ with the sum of ‘CountX’ and ‘mp[PointX[i]]’.
- Similarly, check for ‘PointY’ and both points combined.
Finally, return ‘CountX’ + ‘CountY’ - 2 * ‘CountXY’.

Solve now