Equal Rational Numbers

Problem

Given two strings s and t, each of which represents a non-negative rational number, return true if and only if they represent the same number. The strings may use parentheses to denote the repeating part of the rational number.

A rational number can be represented using up to three parts: <IntegerPart>, <NonRepeatingPart>, and a <RepeatingPart>. The number will be represented in one of the following three ways:

<IntegerPart>
For example, 12, 0, and 123.
- <IntegerPart>**<.>**<NonRepeatingPart>
For example, 0.5, 1., 2.12, and 123.0001.
- <IntegerPart>**<.>**<NonRepeatingPart>**<(>**<RepeatingPart>**<)>**
For example, 0.1(6), 1.(9), 123.00(1212).

The repeating portion of a decimal expansion is conventionally denoted within a pair of round brackets. For example:

1/6 = 0.16666666... = 0.1(6) = 0.1666(6) = 0.166(66).

Examples

Example 1

1
2
3


Input: s = "0.(52)", t = "0.5(25)"
Output: true
Explanation: Because "0.(52)" represents 0.52525252..., and "0.5(25)" represents 0.52525252525..... , the strings represent the same number.

Example 2

1
2


Input: s = "0.1666(6)", t = "0.166(66)"
Output: true

Example 3

1
2
3
4


Input: s = "0.9(9)", t = "1."
Output: true
Explanation: "0.9(9)" represents 0.999999999... repeated forever, which equals 1.  [[See this link for an explanation.](https://en.wikipedia.org/wiki/0.999...)]
"1." represents the number 1, which is formed correctly: (IntegerPart) = "1" and (NonRepeatingPart) = "".

Constraints

Each part consists only of digits.
The <IntegerPart> does not have leading zeros (except for the zero itself).
1 <= <IntegerPart>.length <= 4
0 <= <NonRepeatingPart>.length <= 4
1 <= <RepeatingPart>.length <= 4

Solution

Method 1 – Normalize to Fraction and Compare

Intuition

To check if two rational numbers with possible repeating decimals are equal, convert each to a canonical fraction (numerator/denominator) and compare. This handles all forms, including repeating decimals, by using the formula for the sum of a repeating decimal.

Approach

Parse the string into integer, non-repeating, and repeating parts.
If there is no decimal, treat as integer.
If there is a decimal but no repeating part, treat as a simple decimal.
If there is a repeating part, use the formula:
- Value = IntegerPart + NonRepeatingPart/10^k + RepeatingPart/(10^k * (10^r - 1)), where k = length of non-repeating, r = length of repeating.
Convert the value to a fraction (numerator/denominator) and reduce it.
Compare the two fractions for equality.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


class Solution {
public:
    bool isRationalEqual(string s, string t) {
        auto f = [](const string& str) -> pair<long long, long long> {
            int i = str.find('.'), j = str.find('(');
            string intp = i == string::npos ? str : str.substr(0, i);
            string nonrep = (i == string::npos) ? "" : (j == string::npos ? str.substr(i+1) : str.substr(i+1, j-i-1));
            string rep = j == string::npos ? "" : str.substr(j+1, str.size()-j-2);
            long long num = stoll(intp), den = 1;
            if (!nonrep.empty()) {
                num = num * pow(10, nonrep.size()) + stoll(nonrep);
                den *= pow(10, nonrep.size());
            }
            if (!rep.empty()) {
                long long repnum = stoll(rep);
                int rep_len = rep.size();
                long long repden = pow(10, rep_len) - 1;
                num = num * repden + repnum;
                den *= repden;
            }
            long long g = gcd(num, den);
            return {num/g, den/g};
        };
        auto a = f(s), b = f(t);
        return a == b;
    }
    long long gcd(long long a, long long b) {
        return b ? gcd(b, a % b) : a;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53


import "math/big"

func isRationalEqual(s, t string) bool {
    a := parse(s)
    b := parse(t)
    return a.Cmp(b) == 0
}

func parse(str string) *big.Rat {
    i := strings.Index(str, ".")
    j := strings.Index(str, "(")
    intp := str
    if i != -1 {
        intp = str[:i]
    }
    nonrep := ""
    if i != -1 {
        if j == -1 {
            nonrep = str[i+1:]
        } else {
            nonrep = str[i+1:j]
        }
    }
    rep := ""
    if j != -1 {
        rep = str[j+1 : len(str)-1]
    }
    num := new(big.Int)
    den := big.NewInt(1)
    num.SetString(intp, 10)
    if len(nonrep) > 0 {
        n, _ := new(big.Int).SetString(nonrep, 10)
        num.Mul(num, big.NewInt(int64Pow(10, len(nonrep))))
        num.Add(num, n)
        den.Mul(den, big.NewInt(int64Pow(10, len(nonrep))))
    }
    if len(rep) > 0 {
        r, _ := new(big.Int).SetString(rep, 10)
        repden := big.NewInt(int64Pow(10, len(rep)) - 1)
        num.Mul(num, repden)
        num.Add(num, r)
        den.Mul(den, repden)
    }
    return new(big.Rat).SetFrac(num, den)
}

func int64Pow(a, b int) int64 {
    res := int64(1)
    for i := 0; i < b; i++ {
        res *= int64(a)
    }
    return res
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


class Solution {
    public boolean isRationalEqual(String s, String t) {
        return parse(s).equals(parse(t));
    }
    private Fraction parse(String str) {
        int i = str.indexOf('.'), j = str.indexOf('(');
        String intp = i == -1 ? str : str.substring(0, i);
        String nonrep = i == -1 ? "" : (j == -1 ? str.substring(i+1) : str.substring(i+1, j));
        String rep = j == -1 ? "" : str.substring(j+1, str.length()-1);
        long num = Long.parseLong(intp), den = 1;
        if (!nonrep.isEmpty()) {
            num = num * pow10(nonrep.length()) + Long.parseLong(nonrep);
            den *= pow10(nonrep.length());
        }
        if (!rep.isEmpty()) {
            long repnum = Long.parseLong(rep);
            int rep_len = rep.length();
            long repden = pow10(rep_len) - 1;
            num = num * repden + repnum;
            den *= repden;
        }
        long g = gcd(num, den);
        return new Fraction(num/g, den/g);
    }
    private long pow10(int n) {
        long res = 1;
        for (int i = 0; i < n; i++) res *= 10;
        return res;
    }
    private long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    private static class Fraction {
        long num, den;
        Fraction(long n, long d) { num = n; den = d; }
        public boolean equals(Object o) {
            if (!(o instanceof Fraction)) return false;
            Fraction f = (Fraction)o;
            return num == f.num && den == f.den;
        }
        public int hashCode() { return Long.hashCode(num) ^ Long.hashCode(den); }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


class Solution {
    fun isRationalEqual(s: String, t: String): Boolean {
        fun parse(str: String): Pair<Long, Long> {
            val i = str.indexOf('.')
            val j = str.indexOf('(')
            val intp = if (i == -1) str else str.substring(0, i)
            val nonrep = if (i == -1) "" else if (j == -1) str.substring(i+1) else str.substring(i+1, j)
            val rep = if (j == -1) "" else str.substring(j+1, str.length-1)
            var num = intp.toLong()
            var den = 1L
            if (nonrep.isNotEmpty()) {
                num = num * 10.0.pow(nonrep.length).toLong() + nonrep.toLong()
                den *= 10.0.pow(nonrep.length).toLong()
            }
            if (rep.isNotEmpty()) {
                val repnum = rep.toLong()
                val repden = 10.0.pow(rep.length).toLong() - 1
                num = num * repden + repnum
                den *= repden
            }
            val g = gcd(num, den)
            return num/g to den/g
        }
        fun gcd(a: Long, b: Long): Long = if (b == 0L) a else gcd(b, a % b)
        return parse(s) == parse(t)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


from math import gcd
class Solution:
    def isRationalEqual(self, s: str, t: str) -> bool:
        def parse(x: str) -> tuple[int, int]:
            if '.' not in x:
                return int(x), 1
            i = x.index('.')
            intp = x[:i]
            if '(' in x:
                j = x.index('(')
                nonrep = x[i+1:j]
                rep = x[j+1:-1]
            else:
                nonrep = x[i+1:]
                rep = ''
            num = int(intp) if intp else 0
            den = 1
            if nonrep:
                num = num * 10**len(nonrep) + int(nonrep)
                den *= 10**len(nonrep)
            if rep:
                repnum = int(rep)
                repden = 10**len(rep) - 1
                num = num * repden + repnum
                den *= repden
            g = gcd(num, den)
            return num//g, den//g
        return parse(s) == parse(t)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


impl Solution {
    pub fn is_rational_equal(s: String, t: String) -> bool {
        fn parse(x: &str) -> (i64, i64) {
            let (i, j) = (x.find('.'), x.find('('));
            let intp = if let Some(i) = i { &x[..i] } else { x };
            let nonrep = if let Some(i) = i {
                if let Some(j) = j { &x[i+1..j] } else { &x[i+1..] }
            } else { "" };
            let rep = if let Some(j) = j { &x[j+1..x.len()-1] } else { "" };
            let mut num = intp.parse::<i64>().unwrap_or(0);
            let mut den = 1i64;
            if !nonrep.is_empty() {
                num = num * 10i64.pow(nonrep.len() as u32) + nonrep.parse::<i64>().unwrap();
                den *= 10i64.pow(nonrep.len() as u32);
            }
            if !rep.is_empty() {
                let repnum = rep.parse::<i64>().unwrap();
                let repden = 10i64.pow(rep.len() as u32) - 1;
                num = num * repden + repnum;
                den *= repden;
            }
            let g = num.gcd(&den);
            (num/g, den/g)
        }
        parse(&s) == parse(&t)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


class Solution {
    isRationalEqual(s: string, t: string): boolean {
        function parse(x: string): [bigint, bigint] {
            let i = x.indexOf('.'), j = x.indexOf('(');
            let intp = i === -1 ? x : x.slice(0, i);
            let nonrep = i === -1 ? '' : (j === -1 ? x.slice(i+1) : x.slice(i+1, j));
            let rep = j === -1 ? '' : x.slice(j+1, -1);
            let num = BigInt(intp || '0'), den = 1n;
            if (nonrep) {
                num = num * 10n ** BigInt(nonrep.length) + BigInt(nonrep);
                den *= 10n ** BigInt(nonrep.length);
            }
            if (rep) {
                let repnum = BigInt(rep);
                let repden = 10n ** BigInt(rep.length) - 1n;
                num = num * repden + repnum;
                den *= repden;
            }
            function gcd(a: bigint, b: bigint): bigint {
                return b === 0n ? a : gcd(b, a % b);
            }
            let g = gcd(num, den);
            return [num/g, den/g];
        }
        let a = parse(s), b = parse(t);
        return a[0] === b[0] && a[1] === b[1];
    }
}

Complexity

⏰ Time complexity: O(L) where L is the length of the input strings (parsing and arithmetic are constant for small lengths).
🧺 Space complexity: O(1) (all operations are on small numbers and fixed-length strings).

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – Normalize to Fraction and Compare#

Intuition#

Approach#

Code#

Complexity#