BinarySearch 0667 Number of Fractions that Sum to 1

Problem statement

https://binarysearch.com/problems/Number-of-Fractions-that-Sum-to-1/

Solution

Use canonical representation for each fraction, then use counter.

Complexity

It is O(n log M) for time and O(n) for space.

Code

class Solution:
    def solve(self, F):
        cnt = Counter((x//gcd(x, y), y//gcd(x, y)) for x, y in F)
        ans = 0
        for x, y in cnt:
            if (x, y) == (1, 2):
                ans += cnt[x, y] * (cnt[x, y] - 1)
            else:
                ans += cnt[x, y] * cnt[y - x, y]
        return ans//2