Equal Rational Numbers
HardPrompt
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, and123.
- For example,
<IntegerPart><.><NonRepeatingPart>- For example,
0.5,1.,2.12, and123.0001.
- For example,
<IntegerPart><.><NonRepeatingPart><(><RepeatingPart><)>- For example,
0.1(6),1.(9),123.00(1212).
- For example,
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: trueExample 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 <= 40 <= <NonRepeatingPart>.length <= 41 <= <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
doubleand 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
doubleand return it. - In the main function
isRationalEqual, callconvertToDoublefor both input stringssandt. - Return
trueif the two resultingdoublevalues are equal,falseotherwise.
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
doubleprecision. - Conversion: The expanded string is converted to a
doubleusingDouble.parseDouble(). A crucial observation is thatDouble.parseDouble("0.9999999999999999")evaluates to1.0, which correctly handles cases like0.9(9) == 1. - Comparison: The main function calls this helper for both input strings
sandtand returnstrueif the resultingdoublevalues are equal.
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()); }}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
doubleprecision.It's a 'trick' rather than a fundamentally correct algorithmic solution for comparing rational numbers.
Solutions
Solution
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; }}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.