Equal Rational Numbers

Problem#

Each input string is a non-negative rational like "0.1(6)" (= 1/6). Return true iff the two numbers are equal.

Examples#

"0.(52)", "0.5(25)" → true.
"0.1666(6)", "0.166(66)" → true; "0.9(9)", "1." → true.

Constraints#

Each string length <= 20.

Approach#

Convert each rational to a numerator/denominator pair: parse integer part, non-repeating decimal part, and repeating decimal part; build the fraction algebraically (a + b/10^k + c/(10^k * (10^r - 1))). Compare cross-multiplied.

Solution#

class Solution {
    static pair<long long,long long> reduce(long long n, long long d) {
        long long g = __gcd(n, d);
        return {n / g, d / g};
    }
    static pair<long long,long long> parse(const string& s) {
        long long ip = 0, nr = 0, rp = 0;
        int nrLen = 0, rpLen = 0;
        int i = 0, n = s.size();
        while (i < n && s[i] != '.') ip = ip * 10 + (s[i++] - '0');
        if (i < n && s[i] == '.') ++i;
        while (i < n && s[i] != '(') { nr = nr * 10 + (s[i++] - '0'); ++nrLen; }
        if (i < n && s[i] == '(') {
            ++i;
            while (i < n && s[i] != ')') { rp = rp * 10 + (s[i++] - '0'); ++rpLen; }
        }
        long long p10 = 1;
        for (int k = 0; k < nrLen; ++k) p10 *= 10;
        long long pR = 1;
        for (int k = 0; k < rpLen; ++k) pR *= 10;
        // value = ip + nr / p10 + rp / (p10 * (pR - 1))   [when rpLen > 0]
        long long num, den;
        if (rpLen == 0) {
            num = ip * p10 + nr;
            den = p10;
        } else {
            long long denom = p10 * (pR - 1);
            num = ip * denom + nr * (pR - 1) + rp;
            den = denom;
        }
        return reduce(num, den);
    }
public:
    bool isRationalEqual(string s, string t) {
        auto [a, b] = parse(s);
        auto [c, d] = parse(t);
        return a == c && b == d;
    }
};

func gcd(a, b int64) int64 {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}

func reduce(n, d int64) (int64, int64) {
    g := gcd(n, d)
    return n / g, d / g
}

func parse(s string) (int64, int64) {
    var ip, nr, rp int64
    nrLen, rpLen := 0, 0
    i, n := 0, len(s)
    for i < n && s[i] != '.' {
        ip = ip*10 + int64(s[i]-'0')
        i++
    }
    if i < n && s[i] == '.' {
        i++
    }
    for i < n && s[i] != '(' {
        nr = nr*10 + int64(s[i]-'0')
        nrLen++
        i++
    }
    if i < n && s[i] == '(' {
        i++
        for i < n && s[i] != ')' {
            rp = rp*10 + int64(s[i]-'0')
            rpLen++
            i++
        }
    }
    var p10 int64 = 1
    for k := 0; k < nrLen; k++ {
        p10 *= 10
    }
    var pR int64 = 1
    for k := 0; k < rpLen; k++ {
        pR *= 10
    }
    var num, den int64
    if rpLen == 0 {
        num = ip*p10 + nr
        den = p10
    } else {
        denom := p10 * (pR - 1)
        num = ip*denom + nr*(pR-1) + rp
        den = denom
    }
    return reduce(num, den)
}

func isRationalEqual(s string, t string) bool {
    a, b := parse(s)
    c, d := parse(t)
    return a == c && b == d
}

from math import gcd

class Solution:
    def isRationalEqual(self, s: str, t: str) -> bool:
        def parse(x: str):
            ip = nr = rp = 0
            nr_len = rp_len = 0
            i, n = 0, len(x)
            while i < n and x[i] != '.':
                ip = ip * 10 + int(x[i])
                i += 1
            if i < n and x[i] == '.':
                i += 1
            while i < n and x[i] != '(':
                nr = nr * 10 + int(x[i])
                nr_len += 1
                i += 1
            if i < n and x[i] == '(':
                i += 1
                while i < n and x[i] != ')':
                    rp = rp * 10 + int(x[i])
                    rp_len += 1
                    i += 1
            p10 = 10 ** nr_len
            pR = 10 ** rp_len
            if rp_len == 0:
                num = ip * p10 + nr
                den = p10
            else:
                denom = p10 * (pR - 1)
                num = ip * denom + nr * (pR - 1) + rp
                den = denom
            g = gcd(num, den)
            return num // g, den // g

        return parse(s) == parse(t)

function isRationalEqual(s, t) {
    const gcd = (a, b) => {
        a = a < 0n ? -a : a;
        b = b < 0n ? -b : b;
        while (b !== 0n) [a, b] = [b, a % b];
        return a;
    };
    const parse = (x) => {
        let ip = 0n, nr = 0n, rp = 0n;
        let nrLen = 0, rpLen = 0;
        let i = 0;
        const n = x.length;
        while (i < n && x[i] !== '.') {
            ip = ip * 10n + BigInt(x.charCodeAt(i) - 48);
            i++;
        }
        if (i < n && x[i] === '.') i++;
        while (i < n && x[i] !== '(') {
            nr = nr * 10n + BigInt(x.charCodeAt(i) - 48);
            nrLen++;
            i++;
        }
        if (i < n && x[i] === '(') {
            i++;
            while (i < n && x[i] !== ')') {
                rp = rp * 10n + BigInt(x.charCodeAt(i) - 48);
                rpLen++;
                i++;
            }
        }
        let p10 = 1n;
        for (let k = 0; k < nrLen; k++) p10 *= 10n;
        let pR = 1n;
        for (let k = 0; k < rpLen; k++) pR *= 10n;
        let num, den;
        if (rpLen === 0) {
            num = ip * p10 + nr;
            den = p10;
        } else {
            const denom = p10 * (pR - 1n);
            num = ip * denom + nr * (pR - 1n) + rp;
            den = denom;
        }
        const g = gcd(num, den);
        return [num / g, den / g];
    };
    const [a, b] = parse(s);
    const [c, d] = parse(t);
    return a === c && b === d;
}

class Solution {
    private long gcd(long a, long b) {
        while (b != 0) {
            long t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    private long[] parse(String x) {
        long ip = 0, nr = 0, rp = 0;
        int nrLen = 0, rpLen = 0;
        int i = 0, n = x.length();
        while (i < n && x.charAt(i) != '.') {
            ip = ip * 10 + (x.charAt(i) - '0');
            i++;
        }
        if (i < n && x.charAt(i) == '.') i++;
        while (i < n && x.charAt(i) != '(') {
            nr = nr * 10 + (x.charAt(i) - '0');
            nrLen++;
            i++;
        }
        if (i < n && x.charAt(i) == '(') {
            i++;
            while (i < n && x.charAt(i) != ')') {
                rp = rp * 10 + (x.charAt(i) - '0');
                rpLen++;
                i++;
            }
        }
        long p10 = 1;
        for (int k = 0; k < nrLen; k++) p10 *= 10;
        long pR = 1;
        for (int k = 0; k < rpLen; k++) pR *= 10;
        long num, den;
        if (rpLen == 0) {
            num = ip * p10 + nr;
            den = p10;
        } else {
            long denom = p10 * (pR - 1);
            num = ip * denom + nr * (pR - 1) + rp;
            den = denom;
        }
        long g = gcd(num, den);
        return new long[]{num / g, den / g};
    }

    public boolean isRationalEqual(String s, String t) {
        long[] a = parse(s);
        long[] b = parse(t);
        return a[0] == b[0] && a[1] == b[1];
    }
}

function isRationalEqual(s: string, t: string): boolean {
    const gcd = (a: bigint, b: bigint): bigint => {
        a = a < 0n ? -a : a;
        b = b < 0n ? -b : b;
        while (b !== 0n) [a, b] = [b, a % b];
        return a;
    };
    const parse = (x: string): [bigint, bigint] => {
        let ip = 0n, nr = 0n, rp = 0n;
        let nrLen = 0, rpLen = 0;
        let i = 0;
        const n = x.length;
        while (i < n && x[i] !== '.') {
            ip = ip * 10n + BigInt(x.charCodeAt(i) - 48);
            i++;
        }
        if (i < n && x[i] === '.') i++;
        while (i < n && x[i] !== '(') {
            nr = nr * 10n + BigInt(x.charCodeAt(i) - 48);
            nrLen++;
            i++;
        }
        if (i < n && x[i] === '(') {
            i++;
            while (i < n && x[i] !== ')') {
                rp = rp * 10n + BigInt(x.charCodeAt(i) - 48);
                rpLen++;
                i++;
            }
        }
        let p10 = 1n;
        for (let k = 0; k < nrLen; k++) p10 *= 10n;
        let pR = 1n;
        for (let k = 0; k < rpLen; k++) pR *= 10n;
        let num: bigint, den: bigint;
        if (rpLen === 0) {
            num = ip * p10 + nr;
            den = p10;
        } else {
            const denom = p10 * (pR - 1n);
            num = ip * denom + nr * (pR - 1n) + rp;
            den = denom;
        }
        const g = gcd(num, den);
        return [num / g, den / g];
    };
    const [a, b] = parse(s);
    const [c, d] = parse(t);
    return a === c && b === d;
}

Editorial#

The closed form 0.(r) = r / (10^|r| - 1) lets us turn any repeating decimal into a rational exactly. Reducing each fraction with gcd gives a canonical form; equality becomes a tuple comparison without floating-point pitfalls like 0.(9) == 1.

Complexity#

Time: O(L).
Space: O(1) beyond input.

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#