2001.md

2001. Number of Pairs of Interchangeable Rectangles

Solution 1 (time O(n), space O(n))

class Solution(object):
    def interchangeableRectangles(self, rectangles):
        """
        :type rectangles: List[List[int]]
        :rtype: int
        """
        def gcd(a, b):
            if not b:
                return a
            return gcd(b, a % b)
        
        d = collections.defaultdict(int)
        for a, b in rectangles:
            cur_gcd = gcd(a, b)
            d[(a / cur_gcd, b / cur_gcd)] += 1
        ans = 0
        for k, v in d.items():
            ans += v * (v - 1) / 2
        return ans