Katkat
Back

Find the Largest Equivalence Class of Fractions

Jump TradingSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenStatistics & Math

Last updated

This problem tests your ability to handle numerical equivalence using canonical representations to avoid floating-point precision issues.

Problem Statement

Given a list of fractions, each represented as a pair of integers (numerator, denominator), identify the size of the largest group of fractions that are numerically equivalent. Two fractions a/b and c/d are equivalent if a * d == c * b.

Requirements

  • You must avoid floating-point division to prevent precision errors.
  • Handle fractions with negative values, zero numerators, and large integer inputs.
  • Your solution should output the count of the largest equivalence group.

Function Signature

def largest_equivalence_class(fractions: list[tuple[int, int]]) -> int:
    # fractions is a list of (numerator, denominator)
    pass

Examples

Example 1: Input: [(1, 2), (2, 4), (3, 6), (1, 3)] Output: 3 Explanation: 1/2, 2/4, and 3/6 all equal 0.5.

Example 2: Input: [(0, 5), (0, 1), (5, 0), (10, 0)] Output: 2 Explanation: 0/5 and 0/1 are equivalent (0). 5/0 and 10/0 are equivalent (undefined/infinity).

Constraints

  • fractions list size: n <= 10^5.
  • Numerator/Denominator range: -10^9 to 10^9.
  • Denominator can be 0.

Edge Cases

  • Denominator is 0 (represent as a special case, e.g., (1, 0)).
  • Fractions are negative (e.g., -1/2 vs 1/-2).
  • Numerator is 0 (e.g., 0/1, 0/5).

Hints

Hint 1

To represent each fraction canonically, reduce each pair by dividing the numerator and denominator by their Greatest Common Divisor (GCD).

Hint 2

For negative numbers, ensure the negative sign is always attached to the numerator, and for zero-numerator fractions, use a consistent representation like (0, 1).

Hint 3

Use a hash map (dictionary) to store the canonical (reduced) tuples as keys and their frequencies as values.

Follow-up questions

  • How does your solution change if the denominator can be very large (e.g., exceeding 64-bit integer limits)?
  • What is the time complexity of your approach, and how does the GCD calculation affect it?
  • If the input was a stream of fractions, how would you maintain the 'current' largest class size in real-time?