BinarySearch 0530 Unique Fractions

Problem statement

https://binarysearch.com/problems/Unique-Fractions/

Solution

Use gcd to put number into its canonical form, then sort.

Complexity

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

Code

class Solution:
    def solve(self, F):
        s = set([(x/y, x//gcd(x, y), y//gcd(x, y)) for x, y in F])
        return [(x, y) for _, x, y in sorted(s)]