Equal Rational Numbers - Video Solutions

Problem Overview: Two strings represent rational numbers that may contain repeating decimals using parentheses, such as "0.(52)" or "0.5(25)". The task is to determine whether both strings represent the same numeric value even if their decimal representations look different.

Approach 1: Convert Strings to Fractions (O(n) time, O(1) space)

The reliable way to compare repeating decimals is to convert each string into an exact fraction. Parse the integer part, the non‑repeating decimal part, and the repeating section inside parentheses. A repeating decimal like a.b(c) can be converted using a formula that builds the numerator and denominator from powers of 10. For example, if the non‑repeating section has length k and the repeating section has length r, the denominator becomes 10^k * (10^r - 1). Reduce the resulting fraction using gcd and compare the normalized numerator and denominator for both inputs. This approach avoids floating‑point precision issues and works for all valid representations.

This method relies on careful string parsing and integer arithmetic. You iterate through the string once to extract segments, compute powers of ten, and normalize with gcd. Because only a few integers are stored, the space complexity stays constant. This approach fits well with problems involving math reasoning and precise decimal handling.

Approach 2: Simulate Repetition and Direct Comparison (O(n * k) time, O(k) space)

Another strategy expands the decimal strings by simulating the repeating portion. Parse the repeating block and append it repeatedly until the generated decimal reaches a fixed safe length (commonly around 20–30 digits after the decimal). Do this for both inputs, then compare the resulting normalized decimal strings directly. Because rational numbers eventually repeat, generating enough digits ensures that equivalent values align.

This approach treats the problem primarily as a string manipulation task. You build the decimal representation using concatenation or buffers, pad both results to the same length, and compare characters. It is easier to implement but relies on choosing a sufficiently large repetition length. Time complexity grows with the simulated digits, and extra memory is needed for the constructed strings.

Recommended for interviews: Converting the string representation into reduced fractions is the preferred solution. It runs in O(n) time, avoids precision errors, and demonstrates strong understanding of rational number representation. The simulation approach shows practical reasoning about repeating decimals but is typically considered less robust.