Given a list of integer fractions `(numerator, denominator)`, find the largest number of fractions that represent the same rational value. Fractions may be unreduced, numerators may be negative, and denominators may be negative but not zero. For example, `(1, 2)`, `(2, 4)`, and `(-3, -6)` belong to the same equivalence class, while `(1, -2)` belongs to the class for negative one-half. Describe an algorithm, justify its correctness, and analyze its complexity. Your representation must treat all zero-valued fractions as equal and must not use floating-point division. ### Clarifying Questions to Ask - Can a denominator be zero? For this problem, no. - Are duplicate input pairs counted separately? Yes. - Is the required result only the largest count? Yes, although returning a representative is a natural extension. ### What a Strong Answer Covers - Reduction by the greatest common divisor - A single sign convention - Canonical handling of zero - Why floating point is unsafe for equality - Expected and worst-case complexity ### Follow-up Questions - Return every equivalence class tied for largest. - Support fractions whose numerator and denominator exceed machine integer range. - Process an input stream with bounded memory when only approximate heavy hitters are required.