LeetCode 972: Equal Rational Numbers

Problem Restatement

We are given two strings s and t.

Each string represents a non-negative rational number. A number may be written in one of these forms:

"123"
"123.456"
"123.456(789)"

Parentheses mark the repeating decimal part.

Return true if both strings represent the same rational number. Otherwise, return false.

Examples of equivalent forms:

"0.1(6)" == "0.1666(6)"
"0.9(9)" == "1."

The official note says the integer part length is at most 4, the non-repeating part length is at most 4, and the repeating part length is at most 4. Each part contains only digits, and the integer part does not begin with two or more zeros.

Input and Output

Example function shape:

def isRationalEqual(s: str, t: str) -> bool:
    ...

Examples

Example 1:

s = "0.(52)"
t = "0.5(25)"

Output:

True

Both represent:

0.52525252...

Example 2:

s = "0.1666(6)"
t = "0.166(66)"

Output:

True

Both represent:

0.166666...

Example 3:

s = "0.9(9)"
t = "1."

Output:

True

The value:

0.999999...

equals 1.

First Thought: Use Floating Point

A simple idea is to convert each string into a float and compare with a small tolerance.

That can pass many cases, but it depends on floating-point precision.

This problem is about exact rational equality. A safer method is to convert each string into an exact fraction.

Python has Fraction, which stores rational numbers exactly.

Key Insight

A decimal with a repeating part can be converted into a fraction.

Suppose the number is:

integer.non_repeating(repeating)

Let:

I = integer part
A = non-repeating digits
B = repeating digits
m = len(A)
r = len(B)

The value is:

I + A / 10^m + B / (10^m * (10^r - 1))

Why?

The repeating part:

0.00...00BBBB...

starts after m non-repeating digits.

A repeating block B of length r has value:

B / (10^r - 1)

Then shifting it right by m decimal places divides by:

10^m

So the repeating contribution is:

B / (10^m * (10^r - 1))

Parsing the String

Each input string can have:

1. No decimal point:

"12"

2. A decimal point but no repeating part:

"12.34"
"1."

3. A decimal point and a repeating part:

"12.34(56)"
"1.(9)"

We parse it into:

integer
non_repeating
repeating

If there is no decimal point, both decimal parts are empty.

If there is a decimal point but no parentheses, the repeating part is empty.

Algorithm

Write a helper function parse(value) that returns an exact Fraction.

For each string:

1. Split off the integer part.
2. Extract the non-repeating part.
3. Extract the repeating part if it exists.
4. Start with Fraction(integer, 1).
5. Add the non-repeating decimal part if present.
6. Add the repeating decimal part if present.
7. Compare the two resulting fractions.

Correctness

The helper function separates the string into the three components defined by the problem: integer part, non-repeating decimal part, and repeating decimal part.

The integer part contributes exactly its integer value.

The non-repeating decimal part with m digits contributes its digits divided by 10^m.

The repeating part with r digits contributes a geometric series:

B / 10^(m+r) + B / 10^(m+2r) + B / 10^(m+3r) + ...

The sum of this series is:

B / (10^m * (10^r - 1))

So the helper returns exactly the rational number represented by the string.

The main function converts both inputs to exact fractions and compares them. Two rational numbers are equal if and only if their reduced fractions are equal. Therefore, the algorithm returns True exactly when the two strings represent the same rational number.

Complexity

The input parts have bounded length, but in general let L be the length of the string.

For the official limits, this is effectively constant time.

Implementation

from fractions import Fraction

class Solution:
    def isRationalEqual(self, s: str, t: str) -> bool:
        return self.to_fraction(s) == self.to_fraction(t)

    def to_fraction(self, text: str) -> Fraction:
        if "." not in text:
            return Fraction(int(text), 1)

        integer_part, rest = text.split(".")

        if "(" in rest:
            non_repeating, repeating = rest.split("(")
            repeating = repeating[:-1]
        else:
            non_repeating = rest
            repeating = ""

        value = Fraction(int(integer_part), 1)

        if non_repeating:
            value += Fraction(
                int(non_repeating),
                10 ** len(non_repeating),
            )

        if repeating:
            m = len(non_repeating)
            r = len(repeating)

            value += Fraction(
                int(repeating),
                (10 ** m) * (10 ** r - 1),
            )

        return value

Code Explanation

The main method is short:

return self.to_fraction(s) == self.to_fraction(t)

It converts both strings into exact rational values.

If there is no decimal point:

if "." not in text:
    return Fraction(int(text), 1)

the value is just an integer.

Otherwise, split the integer part from the decimal part:

integer_part, rest = text.split(".")

If the decimal part has parentheses:

if "(" in rest:

we split the non-repeating and repeating parts:

non_repeating, repeating = rest.split("(")
repeating = repeating[:-1]

The last line removes the closing parenthesis.

Start the value with the integer part:

value = Fraction(int(integer_part), 1)

Then add the non-repeating part:

value += Fraction(int(non_repeating), 10 ** len(non_repeating))

Finally, add the repeating part using the exact denominator:

value += Fraction(
    int(repeating),
    (10 ** m) * (10 ** r - 1),
)

Testing

def run_tests():
    s = Solution()

    assert s.isRationalEqual("0.(52)", "0.5(25)") is True
    assert s.isRationalEqual("0.1666(6)", "0.166(66)") is True
    assert s.isRationalEqual("0.9(9)", "1.") is True

    assert s.isRationalEqual("1", "1.0") is True
    assert s.isRationalEqual("1.23", "1.2300") is True
    assert s.isRationalEqual("0.(0)", "0") is True
    assert s.isRationalEqual("0.1(6)", "0.16(6)") is True

    assert s.isRationalEqual("0.1", "0.2") is False
    assert s.isRationalEqual("2.1(3)", "2.13") is False

    print("all tests passed")

run_tests()

Test meaning: