Formatted question description: https://leetcode.ca/all/447.html
447. Number of Boomerangs
Level
Easy
Description
Given n points in the plane that are all pairwise distinct, a “boomerang” is a tuple of points (i, j, k)
such that the distance between i
and j
equals the distance between i
and k
(the order of the tuple matters).
Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [10000, 10000] (inclusive).
Example:
Input: [[0,0],[1,0],[2,0]]
Output: 2
Explanation: The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]
Solution
For each point
in points
, calculate the distance of any other point
to the current point
, and store the number of point
s for each distance. For each distance, if there are k
points, then there are k * (k  1)
boomerangs for the current point
. Calculate the sum to obtain the total number of boomerangs.

class Solution { public int numberOfBoomerangs(int[][] points) { int count = 0; Map<Integer, Integer> map = new HashMap<Integer, Integer>(); int numOfPoints = points.length; for (int i = 0; i < numOfPoints; i++) { map.clear(); int[] point1 = points[i]; for (int j = 0; j < numOfPoints; j++) { if (i == j) continue; int[] point2 = points[j]; int distanceSquare = distanceSquare(point1, point2); int distanceCount = map.getOrDefault(distanceSquare, 0); distanceCount++; map.put(distanceSquare, distanceCount); } Set<Integer> keySet = map.keySet(); for (int key : keySet) { int distanceCount = map.get(key); count += distanceCount * (distanceCount  1); } } return count; } public int distanceSquare(int[] point1, int[] point2) { return (point1[0]  point2[0]) * (point1[0]  point2[0]) + (point1[1]  point2[1]) * (point1[1]  point2[1]); } }

Todo

class Solution(object): def numberOfBoomerangs(self, points): """ :type points: List[List[int]] :rtype: int """ # idea: # we compute the distance starting from any given point and we use a hashtable to count the number of the same distance obtained # once we finish counting distance for one point, we calculate the combinations = 1 * C^1_N * C^1_(N1) ans = 0 for p1 in points: d = {} for p2 in points: if p1 != p2: dist = (p1[0]  p2[0]) ** 2 + (p1[1]  p2[1]) ** 2 d[dist] = d.get(dist, 0) + 1 for k in d: ans += d[k] * (d[k]  1) return ans