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>
12, 0, and 123.<IntegerPart><.><NonRepeatingPart>
0.5, 1., 2.12, and 123.0001.<IntegerPart><.><NonRepeatingPart><(><RepeatingPart><)>
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:
<IntegerPart> does not have leading zeros (except for the zero itself).1 <= <IntegerPart>.length <= 40 <= <NonRepeatingPart>.length <= 41 <= <RepeatingPart>.length <= 4In #972 Equal Rational Numbers, two strings represent rational numbers that may contain repeating decimals written in parentheses, such as 0.(52). The goal is to determine whether both strings represent the same rational value.
A robust approach is to convert each representation into a normalized rational fraction. Parse the integer part, the non‑repeating decimal part, and the repeating section separately. Using mathematical formulas, transform the repeating decimal into a fraction. For example, a repeating block can be represented as the difference between two numbers divided by powers of 10. After forming the numerator and denominator, reduce the fraction using the greatest common divisor (GCD) and compare the two simplified fractions.
An alternative idea is to expand both decimals to a sufficiently long precision and compare them, but the fraction approach is more precise and avoids floating‑point errors. Parsing and fraction construction run in O(n) time where n is the string length, with small constant space overhead.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Parse string and convert repeating decimal to reduced fraction | O(n) | O(1) |
| Expand decimals to fixed precision and compare | O(n) | O(n) |
Math with Mr. J
We can represent each decimal number, potentially with repeating decimals, as a fraction. By converting the number represented by the string into a fraction (numerator and denominator) in a consistent way, we can directly compare the fractions. This involves algebraic manipulation to handle the repeating parts.
For example, 0.1(6) can be represented as 1/6. By converting the repeating part into a fraction, you maintain precision without dealing with floating point inaccuracies. Once both numbers are represented as fractions, compare the fractions as ratios of their numerators and denominators to determine if they represent the same number.
Time Complexity: O(n), where n is the length of the maximum string length, since we handle each character a constant number of times.
Space Complexity: O(1), as we're using a constant amount of additional space for our number components and calculations.
1#include <stdio.h>
2#include <string.h>
3#include <math.h>
4
5long long gcd
This solution defines a function toFraction that converts a string representation of a rational number into its (numerator, denominator) form by interpreting its integer, non-repeating, and repeating sections separately.
The method uses algebraic equivalents for fractions of repeating decimals to convert them. gcd is used to reduce the resulting fraction. Once both numbers are converted, they are compared directly as fractions.
Instead of converting into a fraction, simulate the actual number by expanding it up to a certain number of places where we are confident they will differ if they are indeed different numbers. Focus on accurately reproducing the decimal expansion including the repeating part, and use this expanded version for comparison.
You could use string manipulation to handle the repeat section and use a loop to add the repeating digits until you achieve a sufficient significant length (e.g., 20-30 digits) for a robust comparison.
Time Complexity: O(p), where p is the precision we choose (20 in this case), because we repeatedly generate strings to be compared until this precision is achieved.
Space Complexity: O(p), primarily used to store sequences of the generated decimal until precision is satisfied.
1def expand_decimal(s, precision
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems like #972 Equal Rational Numbers are representative of interview questions at top companies. They test a candidate's understanding of number representation, string parsing, and avoiding floating-point precision issues.
The optimal approach is to parse each number and convert it into a rational fraction. By separating the integer, non-repeating, and repeating parts, you can compute an exact numerator and denominator and reduce them using GCD. If the reduced fractions match, the rational numbers are equal.
The problem mainly relies on mathematical reasoning and string parsing. Using rational number representation with numerator and denominator, along with the GCD algorithm, helps normalize and compare values precisely.
Floating-point numbers introduce rounding errors, especially for repeating decimals. Converting the values to exact fractions avoids precision loss and guarantees accurate comparison of rational numbers.
This solution focuses on simulating the decimal expansion by repeating the portion inside parentheses enough times to ensure that, if the numbers are the same, they will coincide over a sufficient length to determine equality. The expand_decimal function repeats the periodic section until reaching a designated precision and then compares the results much like directly comparing two string values.