# 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:

```python
"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:

```python
"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

| Item | Meaning |
|---|---|
| Input | String `s`, a rational number |
| Input | String `t`, another rational number |
| Output | `true` if both represent the same value |
| Repeating part | Digits inside parentheses repeat forever |

Example function shape:

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

## Examples

Example 1:

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

Output:

```python
True
```

Both represent:

```python
0.52525252...
```

Example 2:

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

Output:

```python
True
```

Both represent:

```python
0.166666...
```

Example 3:

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

Output:

```python
True
```

The value:

```python
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:

```python
integer.non_repeating(repeating)
```

Let:

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

The value is:

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

Why?

The repeating part:

```python
0.00...00BBBB...
```

starts after `m` non-repeating digits.

A repeating block `B` of length `r` has value:

```python
B / (10^r - 1)
```

Then shifting it right by `m` decimal places divides by:

```python
10^m
```

So the repeating contribution is:

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

## Parsing the String

Each input string can have:

1. No decimal point:

```python
"12"
```

2. A decimal point but no repeating part:

```python
"12.34"
"1."
```

3. A decimal point and a repeating part:

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

We parse it into:

```python
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:

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

The sum of this series is:

```python
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.

| Metric | Value | Why |
|---|---|---|
| Time | `O(L)` | We scan and split each string |
| Space | `O(L)` | Parsed substrings and fraction integers |

For the official limits, this is effectively constant time.

## Implementation

```python
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:

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

It converts both strings into exact rational values.

If there is no decimal point:

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

the value is just an integer.

Otherwise, split the integer part from the decimal part:

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

If the decimal part has parentheses:

```python
if "(" in rest:
```

we split the non-repeating and repeating parts:

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

The last line removes the closing parenthesis.

Start the value with the integer part:

```python
value = Fraction(int(integer_part), 1)
```

Then add the non-repeating part:

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

Finally, add the repeating part using the exact denominator:

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

## Testing

```python
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:

| Test | Why |
|---|---|
| `"0.(52)"` vs `"0.5(25)"` | Same repeating value with different split |
| `"0.1666(6)"` vs `"0.166(66)"` | Same repeating sixes |
| `"0.9(9)"` vs `"1."` | Handles repeating nines |
| `"1"` vs `"1.0"` | Integer and decimal equality |
| `"1.23"` vs `"1.2300"` | Trailing zero equality |
| `"0.(0)"` vs `"0"` | Repeating zero |
| `"0.1(6)"` vs `"0.16(6)"` | Same value with shifted repeat |
| `"0.1"` vs `"0.2"` | Different finite decimals |
| `"2.1(3)"` vs `"2.13"` | Repeating decimal differs from finite decimal |