Equal Rational Numbers

Hard

#0926Time: 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.

Patterns

Math

Data structures

String

Prompt

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.]
"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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    public boolean isRationalEqual(String s, String t) {3        return convertToDouble(s) == convertToDouble(t);4    }5 6    private double convertToDouble(String s) {7        int lParen = s.indexOf('(');8        if (lParen == -1) {9            return Double.parseDouble(s);10        }11 12        String nonRepeatingPart = s.substring(0, lParen);13        String repeatingPart = s.substring(lParen + 1, s.length() - 1);14        StringBuilder sb = new StringBuilder(nonRepeatingPart);15        for (int i = 0; i < 20; i++) {16            sb.append(repeatingPart);17        }18        return Double.parseDouble(sb.toString());19    }20}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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:

Parsing: A helper function parses the input string to extract the integer (I), non-repeating (N), and repeating (R) parts.
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| ).
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.
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.

1class Solution {2    class Fraction {3        long num, den;4        public Fraction(long n, long d) {5            long common = gcd(n, d);6            this.num = n / common;7            this.den = d / common;8        }9        private long gcd(long a, long b) {10            return b == 0 ? a : gcd(b, a % b);11        }12    }13 14    public boolean isRationalEqual(String s, String t) {15        Fraction f1 = convertToFraction(s);16        Fraction f2 = convertToFraction(t);17        return f1.num == f2.num && f1.den == f2.den;18    }19 20    private Fraction convertToFraction(String s) {21        int dot = s.indexOf('.');22        if (dot == -1) {23            return new Fraction(Long.parseLong(s), 1);24        }25 26        long intPart = Long.parseLong(s.substring(0, dot));27 28        int lParen = s.indexOf('(');29        if (lParen == -1) { // No repeating part30            String nonRepeating = s.substring(dot + 1);31            if (nonRepeating.isEmpty()) {32                return new Fraction(intPart, 1);33            }34            long den = (long) Math.pow(10, nonRepeating.length());35            long num = Long.parseLong(nonRepeating);36            return new Fraction(intPart * den + num, den);37        }38 39        // Has repeating part40        String nonRepeating = s.substring(dot + 1, lParen);41        String repeating = s.substring(lParen + 1, s.length() - 1);42 43        long den1 = (long) Math.pow(10, nonRepeating.length());44        long den2 = (long) Math.pow(10, repeating.length()) - 1;45        long den = den1 * den2;46        47        long num1 = 0;48        if (!nonRepeating.isEmpty()) {49            num1 = Long.parseLong(nonRepeating);50        }51        long num2 = Long.parseLong(repeating);52        53        // Total fractional part is nonRepeating/den1 + repeating/(den2*den1)54        long totalNum = num1 * den2 + num2;55        56        // Add integer part57        return new Fraction(intPart * den + totalNum, den);58    }59}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  boolean isRationalEqual(String S, String T) {4    int[] rationalS = getRational(S);5    int[] rationalT = getRational(T);6    return rationalS[0] == rationalT[0] && rationalS[1] == rationalT[1];7  }8public9  int[] getRational(String str) {10    boolean positive = true;11    if (str.charAt(0) == '-') {12      str = str.substring(1);13      positive = false;14    }15    int dotIndex = str.indexOf('.');16    if (dotIndex < 0) {17      int integer = Integer.parseInt(str);18      if (!positive)19        integer = -integer;20      int[] rational = {integer, 1};21      return rational;22    }23    int length = str.length();24    if (dotIndex == length - 1) {25      int integer = Integer.parseInt(str.substring(0, dotIndex));26      if (!positive)27        integer = -integer;28      int[] rational = {integer, 1};29      return rational;30    }31    String integerPart = str.substring(0, dotIndex);32    int integer = Integer.parseInt(integerPart);33    String decimalPart = str.substring(dotIndex + 1);34    int decimalPartLength = length - dotIndex - 1;35    int repeatingIndex = str.indexOf('(');36    if (repeatingIndex < 0) {37      int numerator = Integer.parseInt(decimalPart);38      int denominator = (int)Math.pow(10, decimalPartLength);39      int gcd = gcd(numerator, denominator);40      numerator /= gcd;41      denominator /= gcd;42      int[] rational = {numerator, denominator};43      rational[0] += integer * denominator;44      if (!positive)45        rational[0] = -rational[0];46      return rational;47    } else {48      if (repeatingIndex - dotIndex == 1) {49        int numerator =50            Integer.parseInt(str.substring(repeatingIndex + 1, length - 1));51        int denominator = (int)Math.pow(10, decimalPartLength - 2) - 1;52        int gcd = gcd(numerator, denominator);53        numerator /= gcd;54        denominator /= gcd;55        int[] rational = {numerator, denominator};56        rational[0] += integer * denominator;57        if (!positive)58          rational[0] = -rational[0];59        return rational;60      } else {61        int nonRepeatingLength = repeatingIndex - dotIndex - 1;62        int repeatingLength = length - 2 - repeatingIndex;63        int nonRepeating =64            Integer.parseInt(str.substring(dotIndex + 1, repeatingIndex));65        int numerator =66            nonRepeating * (int)Math.pow(10, repeatingLength) +67            Integer.parseInt(str.substring(repeatingIndex + 1, length - 1)) -68            nonRepeating;69        int denominator = (int)(Math.pow(10, repeatingLength) - 1) *70                          (int)(Math.pow(10, nonRepeatingLength));71        int gcd = gcd(numerator, denominator);72        numerator /= gcd;73        denominator /= gcd;74        int[] rational = {numerator, denominator};75        rational[0] += integer * denominator;76        if (!positive)77          rational[0] = -rational[0];78        return rational;79      }80    }81  }82public83  int gcd(int a, int b) {84    if (a == 0 && b == 0)85      return 1;86    while (a > 0 && b > 0) {87      if (a > b) {88        int temp = a;89        a = b;90        b = temp;91      }92      b %= a;93    }94    return a == 0 ? b : a;95  }96}

1# 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 )

1// 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 ; } };

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem