# Equal Rational Numbers
**Difficulty:** HARD
[External](https://leetcode.com/problems/equal-rational-numbers)
Canonical: https://scaleengineer.com/dsa/problems/equal-rational-numbers
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** String
---
## 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)`.

**Example 1:**

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

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

**Example 3:**

**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`

# Approaches
## Convert to Double and Compare
This approach converts each string representation of a rational number into a floating-point `double` and then compares these two `double` values for equality. While generally unsafe due to precision issues with floating-point numbers, it can work for this specific problem because of the small constraints on the lengths of the number parts and the specific behavior of standard library parsing functions.
**Time:** O(1), since the length of the input strings is bounded by a small constant (max length is 4 + 1 + 4 + 1 + 4 = 14). The expansion and parsing operations take a constant amount of time. · **Space:** O(1), as the expanded string created for parsing has a bounded, constant length.
**Pros:** Simple and concise to implement.; Leverages built-in, highly optimized floating-point parsing functions.
**Cons:** Relies on floating-point arithmetic, which is inherently imprecise and generally unsuitable for exact equality checks.; The solution is not robust. It works only because the problem's constraints are small enough to fit within `double` precision.; It's a 'trick' rather than a fundamentally correct algorithmic solution for comparing rational numbers.
### Explanation
The core idea is to approximate the rational number by expanding its decimal representation to a length that exceeds the precision of a `double` (typically 15-17 decimal digits).
A helper function is created to perform this conversion.

- **Parsing:** The input string is parsed to identify the integer, non-repeating, and repeating parts.
- **Expansion:** A new string is built. It starts with the integer part, a decimal point, and the non-repeating part. Then, the repeating part is appended multiple times (e.g., 20 times) to ensure the string is long enough to capture the number's value up to the limit of `double` precision.
- **Conversion:** The expanded string is converted to a `double` using `Double.parseDouble()`. A crucial observation is that `Double.parseDouble("0.9999999999999999")` evaluates to `1.0`, which correctly handles cases like `0.9(9) == 1`.
- **Comparison:** The main function calls this helper for both input strings `s` and `t` and returns `true` if the resulting `double` values are equal.

```java
class Solution {
    public boolean isRationalEqual(String s, String t) {
        return convertToDouble(s) == convertToDouble(t);
    }

    private double convertToDouble(String s) {
        int lParen = s.indexOf('(');
        if (lParen == -1) {
            return Double.parseDouble(s);
        }

        String nonRepeatingPart = s.substring(0, lParen);
        String repeatingPart = s.substring(lParen + 1, s.length() - 1);
        StringBuilder sb = new StringBuilder(nonRepeatingPart);
        for (int i = 0; i < 20; i++) {
            sb.append(repeatingPart);
        }
        return Double.parseDouble(sb.toString());
    }
}
```
### Algorithm
- Define a helper function `convertToDouble(String str)`.
- In the helper function, check if the string contains a repeating part (i.e., a '(' character).
- If there is no repeating part, parse the string directly to a `double` and return it.
- If there is a repeating part, extract the part before the parenthesis (non-repeating) and the part inside the parenthesis (repeating).
- Construct a new string by concatenating the non-repeating part with the repeating part appended enough times (e.g., 20) to saturate the precision of a `double`.
- Parse this newly constructed long string into a `double` and return it.
- In the main function `isRationalEqual`, call `convertToDouble` for both input strings `s` and `t`.
- Return `true` if the two resulting `double` values are equal, `false` otherwise.

## Convert to Fraction and Compare
This approach provides a mathematically robust solution by converting each string representation into its canonical fractional form (p/q). Two rational numbers are equal if and only if their canonical fractions are identical. This method avoids the pitfalls of floating-point imprecision.
**Time:** O(1). The string length is bounded by a constant. Parsing and arithmetic operations on `long`s are constant time. The `gcd` function's complexity is logarithmic with respect to the values, but since the values are bounded by `~10^12`, this is also effectively constant time. · **Space:** O(1). We only need to store a few variables and the `Fraction` objects, which take up constant space.
**Pros:** Mathematically sound and exact. It is the canonical way to compare rational numbers.; Robust and not dependent on floating-point precision limitations. It would work even with much larger constraints by using `BigInteger`.; Handles all cases, including `0.9(9) == 1`, correctly and explicitly through fractional arithmetic.
**Cons:** Implementation is more complex than the floating-point approach, requiring careful handling of fraction arithmetic and GCD calculation.
### Explanation
The fundamental principle is that any terminating or repeating decimal can be expressed as a fraction of two integers. A number represented as `I.N(R)`, where `I` is the integer part, `N` is the non-repeating decimal part, and `R` is the repeating decimal part, can be converted to a fraction using a standard formula.

The algorithm involves:
1.  **Parsing:** A helper function parses the input string to extract the integer (`I`), non-repeating (`N`), and repeating (`R`) parts.
2.  **Fraction Conversion:** It calculates the numerator and denominator of the number. Due to potential size, `long` should be used for these calculations. For a number `I.N(R)`, the value can be expressed as `I + (value of 0.N(R))`. The fractional part `0.N(R)` is equivalent to `(value of NR - value of N) / ( (10^|R| - 1) * 10^|N| )`.
3.  **Simplification:** The resulting fraction (numerator, denominator) is simplified to its canonical form by dividing both parts by their greatest common divisor (GCD). The GCD can be found using the Euclidean algorithm.
4.  **Comparison:** The main function converts both `s` and `t` to their canonical fractions and compares them. If the numerators and denominators are respectively equal, the numbers are the same.

```java
class Solution {
    class Fraction {
        long num, den;
        public Fraction(long n, long d) {
            long common = gcd(n, d);
            this.num = n / common;
            this.den = d / common;
        }
        private long gcd(long a, long b) {
            return b == 0 ? a : gcd(b, a % b);
        }
    }

    public boolean isRationalEqual(String s, String t) {
        Fraction f1 = convertToFraction(s);
        Fraction f2 = convertToFraction(t);
        return f1.num == f2.num && f1.den == f2.den;
    }

    private Fraction convertToFraction(String s) {
        int dot = s.indexOf('.');
        if (dot == -1) {
            return new Fraction(Long.parseLong(s), 1);
        }

        long intPart = Long.parseLong(s.substring(0, dot));

        int lParen = s.indexOf('(');
        if (lParen == -1) { // No repeating part
            String nonRepeating = s.substring(dot + 1);
            if (nonRepeating.isEmpty()) {
                return new Fraction(intPart, 1);
            }
            long den = (long) Math.pow(10, nonRepeating.length());
            long num = Long.parseLong(nonRepeating);
            return new Fraction(intPart * den + num, den);
        }

        // Has repeating part
        String nonRepeating = s.substring(dot + 1, lParen);
        String repeating = s.substring(lParen + 1, s.length() - 1);

        long den1 = (long) Math.pow(10, nonRepeating.length());
        long den2 = (long) Math.pow(10, repeating.length()) - 1;
        long den = den1 * den2;
        
        long num1 = 0;
        if (!nonRepeating.isEmpty()) {
            num1 = Long.parseLong(nonRepeating);
        }
        long num2 = Long.parseLong(repeating);
        
        // Total fractional part is nonRepeating/den1 + repeating/(den2*den1)
        long totalNum = num1 * den2 + num2;
        
        // Add integer part
        return new Fraction(intPart * den + totalNum, den);
    }
}
```
### Algorithm
- Define a helper class `Fraction` to store a numerator and a denominator. The constructor should simplify the fraction by dividing by the GCD.
- Define a helper function `convertToFraction(String str)` that returns a `Fraction` object.
- Inside `convertToFraction`, parse the string to get the integer, non-repeating, and repeating parts.
- Case 1: No decimal point. The fraction is `(Integer, 1)`.
- Case 2: Decimal point, no repeating part (`I.N`). The value is `I + N / 10^|N|`. Convert this to a single fraction `(I * 10^|N| + N) / 10^|N|`.
- Case 3: Decimal point and repeating part (`I.N(R)`). The value is `I + N/10^|N| + R/((10^|R|-1)*10^|N|)`. Combine these into a single fraction. The numerator will be `I * den + N*(10^|R|-1) + R` and the denominator will be `10^|N| * (10^|R|-1)`. Use `long` for calculations to avoid overflow.
- Create a new `Fraction` object with the calculated numerator and denominator, which will also handle simplification via GCD.
- In the main function `isRationalEqual`, call `convertToFraction` for both input strings `s` and `t`.
- Return `true` if the numerators and denominators of the two resulting `Fraction` objects are equal, `false` otherwise.

# Solutions
### Java

```java
class Solution {
public
  boolean isRationalEqual(String S, String T) {
    int[] rationalS = getRational(S);
    int[] rationalT = getRational(T);
    return rationalS[0] == rationalT[0] && rationalS[1] == rationalT[1];
  }
public
  int[] getRational(String str) {
    boolean positive = true;
    if (str.charAt(0) == '-') {
      str = str.substring(1);
      positive = false;
    }
    int dotIndex = str.indexOf('.');
    if (dotIndex < 0) {
      int integer = Integer.parseInt(str);
      if (!positive)
        integer = -integer;
      int[] rational = {integer, 1};
      return rational;
    }
    int length = str.length();
    if (dotIndex == length - 1) {
      int integer = Integer.parseInt(str.substring(0, dotIndex));
      if (!positive)
        integer = -integer;
      int[] rational = {integer, 1};
      return rational;
    }
    String integerPart = str.substring(0, dotIndex);
    int integer = Integer.parseInt(integerPart);
    String decimalPart = str.substring(dotIndex + 1);
    int decimalPartLength = length - dotIndex - 1;
    int repeatingIndex = str.indexOf('(');
    if (repeatingIndex < 0) {
      int numerator = Integer.parseInt(decimalPart);
      int denominator = (int)Math.pow(10, decimalPartLength);
      int gcd = gcd(numerator, denominator);
      numerator /= gcd;
      denominator /= gcd;
      int[] rational = {numerator, denominator};
      rational[0] += integer * denominator;
      if (!positive)
        rational[0] = -rational[0];
      return rational;
    } else {
      if (repeatingIndex - dotIndex == 1) {
        int numerator =
            Integer.parseInt(str.substring(repeatingIndex + 1, length - 1));
        int denominator = (int)Math.pow(10, decimalPartLength - 2) - 1;
        int gcd = gcd(numerator, denominator);
        numerator /= gcd;
        denominator /= gcd;
        int[] rational = {numerator, denominator};
        rational[0] += integer * denominator;
        if (!positive)
          rational[0] = -rational[0];
        return rational;
      } else {
        int nonRepeatingLength = repeatingIndex - dotIndex - 1;
        int repeatingLength = length - 2 - repeatingIndex;
        int nonRepeating =
            Integer.parseInt(str.substring(dotIndex + 1, repeatingIndex));
        int numerator =
            nonRepeating * (int)Math.pow(10, repeatingLength) +
            Integer.parseInt(str.substring(repeatingIndex + 1, length - 1)) -
            nonRepeating;
        int denominator = (int)(Math.pow(10, repeatingLength) - 1) *
                          (int)(Math.pow(10, nonRepeatingLength));
        int gcd = gcd(numerator, denominator);
        numerator /= gcd;
        denominator /= gcd;
        int[] rational = {numerator, denominator};
        rational[0] += integer * denominator;
        if (!positive)
          rational[0] = -rational[0];
        return rational;
      }
    }
  }
public
  int gcd(int a, int b) {
    if (a == 0 && b == 0)
      return 1;
    while (a > 0 && b > 0) {
      if (a > b) {
        int temp = a;
        a = b;
        b = temp;
      }
      b %= a;
    }
    return a == 0 ? b : a;
  }
}

```

### Python

```python
# 972. Equal Rational Numbers # https://leetcode.com/problems/equal-rational-numbers/ class Solution : def isRationalEqual ( self , s : str , t : str ) -> bool : def g ( s ): s2 = "" rep1 = "" ok = False for x in s : if x == "(" or x == ")" : ok = True continue if ok : rep1 += x else : s2 += x return ( s2 , rep1 ) os1 , rep1 = g ( s ) os2 , rep2 = g ( t ) s1 = os1 + rep1 * 30 s2 = os2 + rep2 * 30 if len ( rep1 ) == 0 and len ( rep2 ) == 0 : return s1 == s2 or float ( s1 ) == float ( s2 ) if s1 == s2 or float ( s1 ) == float ( s2 ): return True def good ( s1 , s2 ): count = 1 curr = s1 [ - 1 ] roundCount = len ( s2 ) - 2 for i in range ( len ( s1 ) - 2 , - 1 , - 1 ): if curr == s1 [ i ]: count += 1 else : return False if i > 0 and s1 [ i ] != s1 [ i - 1 ] and count >= 30 : ss = s1 [: i + 1 ] r = float ( ss ) + float ( "0." + "0" * ( len ( ss ) - 3 - bool ( s1 [ i - 1 ] == "." )) + "1" ) if r == float ( s2 ): return True return False return good ( s1 , s2 ) or good ( s2 , s1 )
```

### CPP

```cpp
// OJ: https://leetcode.com/problems/equal-rational-numbers/ // Time: O(1) // Space: O(1) struct Number { string prefix , repeat ; Number ( string p , string r ) : prefix ( p ), repeat ( r ) { int N = r . size (), len = 1 ; // find the minimal repeat part for (; len <= N / 2 ; ++ len ) { int i = 0 ; while ( i < N && repeat [ i ] == repeat [ i % len ]) ++ i ; if ( i == N ) break ; } if ( len <= N / 2 ) repeat = repeat . substr ( 0 , len ); if ( repeat == "0" ) repeat = "" ; normalizePrefix (); } void normalizePrefix () { if ( prefix . find_first_of ( "." ) == string :: npos ) { prefix += '.' ; } else if ( repeat . empty ()) { // only pop trailing zeroes if repeat is empty while ( prefix . back () == '0' ) prefix . pop_back (); } } }; class Solution { string increment ( string & s ) { int i = s . size () - 1 , carry = 1 ; for (; i >= 0 && carry ; -- i ) { if ( s [ i ] == '.' ) continue ; carry += s [ i ] - '0' ; s [ i ] = '0' + carry % 10 ; carry /= 10 ; } if ( carry ) s . insert ( begin ( s ), '1' ); return s ; } Number getNumber ( string & s ) { auto i = s . find_first_of ( "(" ); if ( i == string :: npos ) return Number ( s , "" ); auto ans = Number ( s . substr ( 0 , i ), s . substr ( i + 1 , s . size () - i - 2 )); if ( ans . repeat == "9" ) { ans . repeat = "" ; ans . prefix = increment ( ans . prefix ); ans . normalizePrefix (); } return ans ; } public: bool isRationalEqual ( string s , string t ) { auto a = getNumber ( s ), b = getNumber ( t ); if ( a . repeat . size () != b . repeat . size ()) return false ; if ( a . repeat . size () == 0 ) return a . prefix == b . prefix ; if ( a . prefix . size () > b . prefix . size ()) swap ( a , b ); int i = 0 , N = b . prefix . size (); for (; i < N ; ++ i ) { if ( i < a . prefix . size ()) { if ( a . prefix [ i ] != b . prefix [ i ]) return false ; } else { if ( a . repeat [( i - a . prefix . size ()) % a . repeat . size ()] != b . prefix [ i ]) return false ; } } i = ( i - a . prefix . size ()) % a . repeat . size (); return a . repeat . substr ( i ) + a . repeat . substr ( 0 , i ) == b . repeat ; } };
```