NINJA’S AFFAIR

Moderate

0/80

Average time to solve is 20m

1 upvote

Asked in company

Problem statement

Ninja started using a dating app and he got two matches. Now Ninja becomes greedy and thinks of dating both of them at the same time. So he wants to check the number of the affair points from which the distance between Ninja and both the matches becomes equal.

Given a 2D array/list DISTANCE[i] = [Xi, Yi] of size 'N' x 2, an affair point is defined as a tuple of points ( I, J, K ) such that distance between ‘I’ and ‘J’ equals the distance between ‘I’ and ‘K’.

As Ninja is busy getting ready for his date, he asks you for help. So your task is to find the numbers of affair points.

Note:

1. The distance between two points (X1, Y1) and (X2, Y2) is calculated as [ (X1 - X2) ^ 2 + (Y1 - Y2) ^ 2 ] i.e without a square root. 
2. The order of tuples matters.

Example:

Suppose the given 'DISTANCE' array/list is [ [ 0, 0 ], [ 1, 0 ], [ 2, 0 ] ]. We return ‘2’as the answer as only two affair points are there as follows:  

[ [ 1, 0 ], [ 0, 0 ], [ 2, 0 ] as ( ( 0 - 1) * ( 0 - 1 ) + (0 - 0 ) * ( 0 - 0 ) = ( 2 - 1 ) * ( 2 - 1 ) + ( 0 - 0 ) * ( 0 - 0 ) = 1
Distance of [1, 0] is same for [0, 0] and [2, 0].

[ [ 1, 0 ], [ 2, 0 ], [ 0, 0 ] ] as ( ( 2 - 1 ) * ( 2 - 1 ) + ( 0 - 0 ) * ( 0 - 0 ) = ( 0- 1 ) * ( 0 - 1 ) + ( 0 - 0 ) * ( 0 - 0 )
Distance of [1, 0] is same for [2, 0] and [0, 0].

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains the ‘T’ number of test cases.

The first line of each test case contains an integer ‘N’ denoting the number of points in the ‘DISTANCE’ list/array. Then, ‘N’ lines follow.

Each line contains two space-separated integers denoting the points ‘Xi, Yi’.

Output Format:

For each test case, print a single line containing a single integer denoting the total number of possible affair points.

The output of each test case will be printed in a separate line.

Note:

You are not required to print anything explicitly. It has already been taken care of. Just implement the function.

Constraints:

1 <= ‘T’ <= 50
1 <= ‘N’ <= 100
-10000 <= ‘DISTANCE[i][0]’, 'DISTANCE[i][1] <= 10000   

Where ‘T’ represents the number of test cases, ‘N’ represents the size of the ‘DISTANCE’ array/list, and 'DISTANCE[i][0]' represents the point 'Xi' and 'DISTANCE[i][1]' represents the point 'Yi'.

Time Limit: 1 sec.

Sample Input 1:

Sample Output 1:

2
2

Explanation of Sample Input 1:

Test Case 1:

The  'DISTANCE' array/list is [ [ 3, 0 ], [ 1, 0 ], [ 2, 0 ] ]. We return ‘2’ as the answer as only two affair points are there i.e  [ [ 2, 0 ], [ 1, 0 ], [ 3, 0 ] ] and [ [ 2, 0 ], [ 3, 0 ], [ 1, 0 ] ].
For the first affair point, ‘I’ is [ 2, 0 ], ‘J’ is[ 1, 0 ] and ‘K’  is [ 3, 0 ].
For the second affair point, ‘I’ is [ 2, 0 ], ‘J’ is[ 3, 0 ] and ‘K’ is[ 1, 0 ]. 
By using the distance formula, we can say that distance between ‘I’ to ‘J’ and ‘I’ to ‘K’ is equal.

Test Case 2:

The 'DISTANCE' array is [ [ 1, 1 ], [ 2, 2 ], [ 3, 3 ] ]. We return ‘4’ as the answer as only two affair points are there i.e  [ [ 2, 2 ], [ 1, 1 ], [ 3, 3 ] ] and [ [ 2, 2 ], [ 3, 3 ], [ 1, 1 ] ]. 
By using distance formula we can say that distance between ‘I’ to ‘J’ and ‘I’ to ‘K’ is equal.

Sample Input 2:

Sample Output 2:

0
4

Hint 1

Hint 2

Can you check all the possible combinations?

Approaches (2)

Approach 1

Approach 2

Brute Force Approach

The idea here is to use the brute force approach and check for each and every possible pair. If there is any pair of points satisfying the given condition of being an affair point, we increase the count by ‘1’.

First, we declare a variable named ‘COUNT = 0’ and initialize it with ‘0’.
Run a loop where ‘i’ ranges from ‘0’ to ‘N’.
- Run another loop where ‘j’ ranges from ‘0’ to ‘N’.
  - If ‘j’ == ‘i’ continue the loop.
  - Else run another loop where ‘k’ ranges from ‘0’ to ‘N’
    - If ‘k’ == ‘j’ continue the loop.
    - Compare the distance of point ‘i’ to ‘j’ and ‘i’ to ‘k’.
      - If the distance is equal, increase ‘COUNT’ by ‘1’.
Return the ‘COUNT’.

Time Complexity

O(N ^ 3), where ‘N’ is the size of the array/list ‘DISTANCE’.

As we are iterating through our array using three nested loops and each loop runs for the size of the array.

Space Complexity

O(1).

Since we are using constant space.

(100% EXP penalty)

NINJA’S AFFAIR

Console