447.Number of Boomerangs

Tags: [map], [math]

Link: https://leetcode.com/problems/number-of-boomerangs/?tab=Description

Givennpoints in the plane that are all pairwise distinct, a "boomerang" is a tuple of points(i, j, k)such that the distance betweeniandjequals the distance betweeniandk(the order of the tuple matters).

Find the number of boomerangs. You may assume thatnwill be at most500and 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: map and math

import math

class Solution(object):
    def numberOfBoomerangs(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        if not points:
            return 0

        num_of_points = len(points)
        counter = 0
        for i in xrange(num_of_points):
            # pick up one of the points as the point i.
            distance_map = {}
            for j in xrange(num_of_points):
                if i == j:
                    continue

                distance = self.distance(points[i], points[j])
                if distance not in distance_map:
                    distance_map[distance] = 1
                else:
                    distance_map[distance] += 1

            for key in distance_map:
                n = distance_map[key]
                # counter += (choose 2 from n) multiply (permutation 2), 
                # which can be simplify to n * (n - 1)
                counter += n * (n - 1)

        return counter;

    def distance(self, point_1, point_2):
        return math.sqrt((point_1[0] - point_2[0]) ** 2 + (point_1[1] - point_2[1]) ** 2)

Revelation:

• If point A has the same distance to the points B, C, D, so there will be (A, B, C), (A, C, B), (A, B, D), (A, D, B), (A, C, D), (A, D, C), which can be simplify to (B, C), (C, B), (B, D), (D, B), (C, D), (D, C), which is that choose 2 points from B, C, D, and then do the permutation on these two chosen points. So the number of the unique sequence is (choose 2 from n) * (permutation 2) = (n! / 2! * (n - 2)!) * 2 = (n! / 2 * (n - 2)!) * 2 = n! / (n - 2)! = n * (n - 1) * (n - 2)! / (n - 2)! = n * (n - 1).
• Do not forget to use math to simplify the calculation.

Note:

• Time complexity = O(n^2), n is the number of the given points.
• In Python, use math.sqrt() to calculate the square root.
• In Python, n^2 == n**2
• The factorial of n = n * (n - 1) * (n - 2) * ... * 1. It can be coded by recursion, cannot apply DP on it.

def factorial(n):
    # base case
    if n == 1:
        return 1
    return n * factorial(n - 1)

Time Limited Exceeded

import math

class Solution(object):
    def numberOfBoomerangs(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        if not points or len(points) < 3:
            return 0

        num_of_points = len(points)
        counter = 0
        for i in xrange(num_of_points):
            for j in xrange(num_of_points):
                for k in xrange(num_of_points):
                    if i != j and i != k and j != k and\
                       self.distance(points[i], points[j]) == self.distance(points[i], points[k]):
                           counter += 1

        return counter

    def distance(self, point_1, point_2):
        return math.sqrt((point_1[0] - point_2[0]) ** 2 + (point_1[1] - point_2[1]) ** 2)

Note:

• Time complexity = O(n^3), n is the number of the given points.