Algorithm
Problem Name: 447. Number of Boomerangs
Problem Link: https://leetcode.com/problems/number-of-boomerangs/
You are given n points in the plane that are all distinct, where points[i] = [xi, yi]. 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).
Return the number of boomerangs.
Example 1:
Input: points = [[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]].
Example 2:
Input: points = [[1,1],[2,2],[3,3]] Output: 2
Example 3:
Input: points = [[1,1]] Output: 0
Constraints:
n == points.length1 <= n <= 500points[i].length == 2-104 <= xi, yi <= 104- All the points are unique.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#define DUMP(P, I, J, K) do { } while (0)
int dis(int **p, int a, int b) {
int x = abs(p[a][0] - p[b][0]);
int y = abs(p[a][1] - p[b][1]);
int z = x * x + y * y;
return z;
}
int numberOfBoomerangs(int** points, int pointsRowSize, int pointsColSize) {
int n = 0;
int i, j, k;
double d1, d2;
for (i = 0; i < pointsRowSize; i ++) {
for (j = 0; j < pointsRowSize; j ++) {
if (j == i) continue;
d1 = dis(points, i, j);
for (k = j + 1; k < pointsRowSize; k ++) {
d2 = dis(points, i, k);
if (d1 == d2) {
DUMP(points, i, j, k);
n ++;
}
}
}
}
return n * 2;
}
Input
points = [[0,0],[1,0],[2,0]]
Output
2
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const numberOfBoomerangs = function(points) {
const m = new Map()
const len = points.length
let res = 0
for(let i = 0; i < len; i++) {
for(let j = 0; j < len; j++) {
if(i === j) continue
const d = dis(points[i], points[j])
if(!m.has(d)) m.set(d, 0)
m.set(d, m.get(d) + 1)
}
for(let v of m.values()) {
res += v * (v - 1)
}
m.clear()
}
return res
};
function dis(a, b) {
return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2
}
Input
points = [[0,0],[1,0],[2,0]]
Output
2
#3 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Collections.Generic;
namespace LeetCode
{
public class _0447_NumberOfBoomerangs
{
public int NumberOfBoomerangs(int[][] points)
{
var count = 0;
foreach (var point1 in points)
{
var distMap = new Dictionary < int, int>();
foreach (var point2 in points)
{
int distSq = (int)Math.Pow(point1[0] - point2[0], 2) + (int)Math.Pow(point1[1] - point2[1], 2);
if (!distMap.ContainsKey(distSq))
distMap.Add(distSq, 1);
else
count += distMap[distSq]++;
}
}
return count * 2;
}
}
}
Input
points = [[1,1],[2,2],[3,3]]
Output
2