equals/hashCode — Fraction Class

Problem

Build a Fraction(int num, int den) class with overridden equals and hashCode so that mathematically-equal fractions (e.g. 1/2 and 2/4) compare equal and live in the same HashSet bucket. Given a list of (num, den) pairs, return the size of the deduped HashSet.

Constraints

• 1 ≤ list.size() ≤ 1000
• denominator != 0

Approach — Hashing & Counting

This is a Hashing & Counting problem. The idea: store what you've seen in a hash map for O(1) lookups, trading a little space to avoid a nested scan. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n) time, O(n) space.

Solution code

Python

class Solution:
    def distinctFractions(self, pairs):
        from math import gcd
        seen = set()
        for a, b in pairs:
            g = gcd(a, b) or 1
            seen.add((a // g, b // g))
        return len(seen)

Java

import java.util.*;

class Fraction {
    int num, den;
    Fraction(int num, int den) {
        int g = gcd(Math.abs(num), Math.abs(den));
        if (g == 0) g = 1;
        int sign = (num < 0) ^ (den < 0) ? -1 : 1;
        this.num = sign * Math.abs(num) / g;
        this.den = Math.abs(den) / g;
    }
    private static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
    @Override public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Fraction)) return false;
        Fraction f = (Fraction) o;
        return num == f.num && den == f.den;
    }
    @Override public int hashCode() { return Objects.hash(num, den); }
}

class Solution {
    public int distinctFractions(int[][] pairs) {
        Set<Fraction> s = new HashSet<>();
        for (int[] p : pairs) s.add(new Fraction(p[0], p[1]));
        return s.size();
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.