Equal Rational Numbers solution and explanation
Google
6 more videos on this problem
花花酱 LeetCode 972. Equal Rational Numbers - 刷题找工作 EP239Hua Hua · 15:25 · 1K views
972. Equal Rational Numbers (Leetcode Hard)Programming Live with Larry · 26:55 · 113 views
No Sound Leetcode 972: Equal Rational NumbersExtremeProgrammer · 3:04 · 28 views
LeetCode 972: Equal Rational NumbersAlitaCode · 30:24 · 3 views
LeetCode 972: Equal Rational NumbersAlitaCode · 31:44 · 2 views
LeetCode Problem #972 Equal Rational Numbers神戸万事屋 · 0:57
LeetCode Problem #972 Equal Rational Numbers神戸万事屋 · 1:49
The 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, 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: 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 <= 40 <= <NonRepeatingPart>.length <= 41 <= <RepeatingPart>.length <= 4
Approach overview
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.
Approach 1: Convert Strings to Fractions
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.
from math import gcd
def split_number(s):
int_part, non_repeat, repeat = 0, 0, 0
non_repeat_len, repeat_len = 0, 0
int_part_read = True
i = 0
while i < len(s):
if s[i].isdigit():
if int_part_read:
int_part = int_part * 10 + int(s[i])
elif repeat_len == 0:
non_repeat = non_repeat * 10 + int(s[i])
non_repeat_len += 1
else:
repeat = repeat * 10 + int(s[i])
repeat_len += 1
elif s[i] == '.':
int_part_read = False
elif s[i] == '(':
repeat_len = 1
i += 1
return int_part, non_repeat, repeat, non_repeat_len, repeat_len
def to_fractional(s):
int_part, non_repeat, repeat, non_repeat_len, repeat_len = split_number(s)
if repeat_len == 0:
numerator = int_part * 10 ** non_repeat_len + non_repeat
denominator = 10 ** non_repeat_len
else:
pow_nr10 = 10 ** non_repeat_len
pow_r10 = 10 ** repeat_len
numerator = int_part * pow_nr10 * (pow_r10 - 1) + non_repeat * (pow_r10 - 1) + repeat
denominator = pow_nr10 * (pow_r10 - 1)
common_div = gcd(numerator, denominator)
numerator //= common_div
denominator //= common_div
return numerator, denominator
def is_equal_rational(s, t):
num_s, den_s = to_fractional(s)
num_t, den_t = to_fractional(t)
return num_s == num_t and den_s == den_t
# Example usage
s = "0.(52)"
t = "0.5(25)"
print("true" if is_equal_rational(s, t) else "false")import java.util.*;
class RationalNumberComparer {
private long gcd(long a, long b) {
return b == 0 ? a : gcd(b, a % b);
}
private void splitNumber(String s, long[] parts) {
long intPart = 0, nonRepeat = 0, repeat = 0;
int nonRepeatLen = 0, repeatLen = 0;
boolean intPartRead = true;
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) {
if (intPartRead) intPart = intPart * 10 + (c - '0');
else if (repeatLen == 0) nonRepeat = nonRepeat * 10 + (c - '0'); nonRepeatLen++;
else repeat = repeat * 10 + (c - '0'); repeatLen++;
} else if (c == '.') {
intPartRead = false;
} else if (c == '(') {
repeatLen = 1;
}
}
parts[0] = intPart; parts[1] = nonRepeat; parts[2] = repeat; parts[3] = nonRepeatLen; parts[4] = repeatLen;
}
private long[] toFraction(String s) {
long[] parts = new long[5];
splitNumber(s, parts);
long numerator, denominator;
if (parts[4] == 0) { // no repeat part
numerator = parts[0] * (long) Math.pow(10, parts[3]) + parts[1];
denominator = (long) Math.pow(10, parts[3]);
} else {
long powNR10 = (long) Math.pow(10, parts[3]);
long powR10 = (long) Math.pow(10, parts[4]);
numerator = parts[0] * powNR10 * (powR10 - 1) + parts[1] * (powR10 - 1) + parts[2];
denominator = powNR10 * (powR10 - 1);
}
long commonDiv = gcd(numerator, denominator);
return new long[]{numerator / commonDiv, denominator / commonDiv};
}
public boolean isEqualRational(String s, String t) {
long[] fracS = toFraction(s);
long[] fracT = toFraction(t);
return fracS[0] == fracT[0] && fracS[1] == fracT[1];
}
public static void main(String[] args) {
RationalNumberComparer rnc = new RationalNumberComparer();
String s = "0.(52)", t = "0.5(25)";
System.out.println(rnc.isEqualRational(s, t) ? "true" : "false");
}
}#include <iostream>
#include <string>
#include <cmath>
long long gcd(long long a, long long b) {
return b == 0 ? a : gcd(b, a % b);
}
void splitNumber(const std::string &s, long long &intPart, long long &nonRepeat, long long &repeat, int &nonRepeatLen, int &repeatLen) {
intPart = 0;
nonRepeat = 0;
repeat = 0;
nonRepeatLen = 0;
repeatLen = 0;
bool intPartRead = true;
for (char c : s) {
if (isdigit(c)) {
if (intPartRead) intPart = intPart * 10 + (c - '0');
else if (repeatLen == 0) nonRepeat = nonRepeat * 10 + (c - '0'), ++nonRepeatLen;
else repeat = repeat * 10 + (c - '0'), ++repeatLen;
} else if (c == '.') {
intPartRead = false;
} else if (c == '(') {
repeatLen = 1;
}
}
}
void toFraction(const std::string &s, long long &numerator, long long &denominator) {
long long intPart, nonRepeat, repeat;
int nonRepeatLen, repeatLen;
splitNumber(s, intPart, nonRepeat, repeat, nonRepeatLen, repeatLen);
if (repeatLen == 0) { // no repeat part
numerator = intPart * std::pow(10, nonRepeatLen) + nonRepeat;
denominator = std::pow(10, nonRepeatLen);
} else {
long long powNR10 = std::pow(10, nonRepeatLen);
long long powR10 = std::pow(10, repeatLen);
numerator = intPart * powNR10 * (powR10 - 1) + nonRepeat * (powR10 - 1) + repeat;
denominator = powNR10 * (powR10 - 1);
}
long long commonDiv = gcd(numerator, denominator);
numerator /= commonDiv;
denominator /= commonDiv;
}
bool isEqualRational(const std::string &s, const std::string &t) {
long long numS, denS, numT, denT;
toFraction(s, numS, denS);
toFraction(t, numT, denT);
return numS == numT && denS == denT;
}
int main() {
std::string s = "0.(52)", t = "0.5(25)";
if (isEqualRational(s, t)) std::cout << "true" << std::endl;
else std::cout << "false" << std::endl;
return 0;
}function gcd(a, b) {
return b === 0 ? a : gcd(b, a % b);
}
function splitNumber(s) {
let intPart = 0, nonRepeat = 0, repeat = 0;
let nonRepeatLen = 0, repeatLen = 0;
let intPartRead = true;
for (let i = 0; i < s.length; i++) {
let char = s[i];
if (char >= '0' && char <= '9') {
if (intPartRead) intPart = intPart * 10 + (char - '0');
else if (repeatLen === 0) nonRepeat = nonRepeat * 10 + (char - '0'), nonRepeatLen++;
else repeat = repeat * 10 + (char - '0'), repeatLen++;
} else if (char === '.') {
intPartRead = false;
} else if (char === '(') {
repeatLen = 1;
}
}
return { intPart, nonRepeat, repeat, nonRepeatLen, repeatLen };
}
function toFraction(s) {
const { intPart, nonRepeat, repeat, nonRepeatLen, repeatLen } = splitNumber(s);
let numerator, denominator;
if (repeatLen === 0) {
numerator = intPart * Math.pow(10, nonRepeatLen) + nonRepeat;
denominator = Math.pow(10, nonRepeatLen);
} else {
const powNR10 = Math.pow(10, nonRepeatLen);
const powR10 = Math.pow(10, repeatLen);
numerator = intPart * powNR10 * (powR10 - 1) + nonRepeat * (powR10 - 1) + repeat;
denominator = powNR10 * (powR10 - 1);
}
const commonDiv = gcd(numerator, denominator);
numerator /= commonDiv;
denominator /= commonDiv;
return { numerator, denominator };
}
function isEqualRational(s, t) {
const fracS = toFraction(s);
const fracT = toFraction(t);
return fracS.numerator === fracT.numerator && fracS.denominator === fracT.denominator;
}
// Example usage
const s = '0.(52)';
const t = '0.5(25)';
console.log(isEqualRational(s, t) ? 'true' : 'false');#include <stdio.h>
#include <string.h>
#include <math.h>
long long gcd(long long a, long long b) {
return b == 0 ? a : gcd(b, a % b);
}
void splitNumber(const char *s, long long *intPart, long long *nonRepeat, long long *repeat, int *nonRepeatLen, int *repeatLen) {
*intPart = 0; *nonRepeat = 0; *repeat = 0;
*nonRepeatLen = 0; *repeatLen = 0;
int intPartRead = 1;
for (int i = 0; s[i]; ++i) {
if (s[i] >= '0' && s[i] <= '9') {
if (intPartRead) *intPart = *intPart * 10 + (s[i] - '0');
else if (*repeatLen == 0) *nonRepeat = *nonRepeat * 10 + (s[i] - '0'), (*nonRepeatLen)++;
else *repeat = *repeat * 10 + (s[i] - '0'), (*repeatLen)++;
} else if (s[i] == '.') {
intPartRead = 0;
} else if (s[i] == '(') {
*repeatLen = 1; // start reading repeat
}
}
}
void toFraction(const char *s, long long *numerator, long long *denominator) {
long long intPart, nonRepeat, repeat;
int nonRepeatLen, repeatLen;
splitNumber(s, &intPart, &nonRepeat, &repeat, &nonRepeatLen, &repeatLen);
if (repeatLen == 0) { // no repeat part
*numerator = intPart * pow(10, nonRepeatLen) + nonRepeat;
*denominator = pow(10, nonRepeatLen);
} else {
long long powNR10 = pow(10, nonRepeatLen);
long long powR10 = pow(10, repeatLen);
*numerator = intPart * powNR10 * (powR10 - 1) + nonRepeat * (powR10 - 1) + repeat;
*denominator = powNR10 * (powR10 - 1);
}
long long commonDiv = gcd(*numerator, *denominator);
*numerator /= commonDiv;
*denominator /= commonDiv;
}
int isEqualRational(const char *s, const char *t) {
long long numS, denS, numT, denT;
toFraction(s, &numS, &denS);
toFraction(t, &numT, &denT);
return numS == numT && denS == denT;
}
int main() {
char s[] = "0.(52)", t[] = "0.5(25)";
if (isEqualRational(s, t)) printf("true\n");
else printf("false\n");
return 0;
}using System;
public class RationalNumberComparer {
private static long Gcd(long a, long b) {
return b == 0 ? a : Gcd(b, a % b);
}
private void SplitNumber(string s, out long intPart, out long nonRepeat, out long repeat, out int nonRepeatLen, out int repeatLen) {
intPart = 0;
nonRepeat = 0;
repeat = 0;
nonRepeatLen = 0;
repeatLen = 0;
bool intPartRead = true;
foreach (char c in s) {
if (char.IsDigit(c)) {
if (intPartRead) intPart = intPart * 10 + (c - '0');
else if (repeatLen == 0) nonRepeat = nonRepeat * 10 + (c - '0'); nonRepeatLen++;
else repeat = repeat * 10 + (c - '0'); repeatLen++;
} else if (c == '.') {
intPartRead = false;
} else if (c == '(') {
repeatLen = 1;
}
}
}
private void ToFraction(string s, out long numerator, out long denominator) {
long intPart, nonRepeat, repeat;
int nonRepeatLen, repeatLen;
SplitNumber(s, out intPart, out nonRepeat, out repeat, out nonRepeatLen, out repeatLen);
if (repeatLen == 0) {
numerator = intPart * (long)Math.Pow(10, nonRepeatLen) + nonRepeat;
denominator = (long)Math.Pow(10, nonRepeatLen);
} else {
long powNR10 = (long)Math.Pow(10, nonRepeatLen);
long powR10 = (long)Math.Pow(10, repeatLen);
numerator = intPart * powNR10 * (powR10 - 1) + nonRepeat * (powR10 - 1) + repeat;
denominator = powNR10 * (powR10 - 1);
}
long commonDiv = Gcd(numerator, denominator);
numerator /= commonDiv;
denominator /= commonDiv;
}
public bool IsEqualRational(string s, string t) {
ToFraction(s, out long numS, out long denS);
ToFraction(t, out long numT, out long denT);
return numS == numT && denS == denT;
}
public static void Main() {
RationalNumberComparer rnc = new RationalNumberComparer();
string s = "0.(52)", t = "0.5(25)";
Console.WriteLine(rnc.IsEqualRational(s, t) ? "true" : "false");
}
}The Python implementation follows the same logic as the previous solutions. It extracts different number parts into integers and then calculates the numerator and denominator for each string using those parts. The differences in Python allow us to directly manipulate integers without worrying about overflow, and utilize Python's gcd from the math module to simplify the fraction, making the comparison straightforward.
Time Complexity: O(n), where n is the maximum length of the input strings, because we iterate over each character individually.
Space Complexity: O(1), as the additional space required doesn't grow with input size, keeping the space fixed.
Approach 2: Simulate Repetition and Direct Comparison
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.
def expand_decimal(s, precision=20):
before_repeat, repeat = s.strip(')').split('(') if '(' in s else (s, '')
expanded = before_repeat
# Add the repeat part enough times
while len(expanded) <= precision:
expanded += repeat
return expanded
def remove_leading_trailing_zeros(s):
s = s.rstrip('0').rstrip('.')
return s.lstrip('0') or '0'
def is_equal_up_to_precision(s, t, precision=20):
s_expanded = expand_decimal(s, precision)
t_expanded = expand_decimal(t, precision)
return remove_leading_trailing_zeros(s_expanded) == remove_leading_trailing_zeros(t_expanded)
# Example usage
s = "0.(52)"
t = "0.5(25)"
print("true" if is_equal_up_to_precision(s, t) else "false")function expandDecimal(s, precision = 20) {
const parts = s.split('(');
const beforeRepeat = parts[0];
const repeat = parts.length > 1 ? parts[1].slice(0, -1) : '';
let expanded = beforeRepeat;
while (expanded.length <= precision) {
expanded += repeat;
}
// Remove leading and trailing zeroes for comparison
return expanded.replace(/^0+/, '') || '0';
}
function isEqualUpToPrecision(s, t, precision = 20) {
const sExpanded = expandDecimal(s, precision);
const tExpanded = expandDecimal(t, precision);
return sExpanded === tExpanded;
}
const s = "0.(52)";
const t = "0.5(25)";
console.log(isEqualUpToPrecision(s, t) ? 'true' : 'false');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.
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.
Complexity comparison
| Approach | Complexity |
|---|---|
| Convert Strings to Fractions | Time Complexity: O(n), where n is the maximum length of the input strings, because we iterate over each character individually. Space Complexity: O(1), as the additional space required doesn't grow with input size, keeping the space fixed. |
| Simulate Repetition and Direct 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. |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Convert Strings to Fractions | O(n) | O(1) | Best general solution; exact comparison without floating‑point errors |
| Simulate Repetition and Compare | O(n * k) | O(k) | Useful for quick implementation using string expansion of repeating parts |
Frequently asked questions
Is Equal Rational Numbers easy or hard?
Equal Rational Numbers is classified as a Hard problem. The difficulty comes from correctly handling repeating decimal patterns and converting them into exact fractions without floating‑point rounding issues. Strong math reasoning and careful string parsing are required.
Equal Rational Numbers Python/Java solution
In Python or Java, parse the string sections and compute the fraction using integer math. Python benefits from arbitrary‑precision integers, while Java implementations typically use long values with gcd normalization. Both languages follow the same O(n) fraction conversion strategy.
How to solve Equal Rational Numbers in O(n)?
Parse the rational number into three parts: integer portion, non‑repeating decimal, and repeating cycle. Use a mathematical formula to convert the repeating decimal into a fraction with denominator 10^k * (10^r − 1). Reduce the fraction using gcd and compare both normalized fractions. The parsing step is linear in the string length, giving O(n) time.
What is the best approach for Equal Rational Numbers?
The best approach converts each rational number string into a reduced fraction. Parse the integer part, non‑repeating decimals, and repeating section, then compute the exact numerator and denominator using powers of 10. After reducing with gcd, simply compare the fractions. This runs in O(n) time and avoids floating‑point precision errors.
Is Equal Rational Numbers asked at Google/Amazon/Meta?
This problem is categorized as a hard math and string parsing problem and appears in advanced interview practice sets similar to those used by companies like Google and Meta. It tests understanding of rational number representation, precise arithmetic, and careful string parsing.
What data structure is used in Equal Rational Numbers?
The solution primarily uses string parsing and integer arithmetic rather than complex data structures. Variables store the integer, non‑repeating, and repeating segments, and mathematical operations convert them into a fraction. Some implementations also use helper functions like gcd for fraction reduction.
What is the time complexity of Equal Rational Numbers?
The optimal fraction conversion solution runs in O(n) time where n is the length of the input string. Each string is parsed once and constant‑time arithmetic operations are applied to compute the numerator and denominator. Space complexity is O(1) because only a few integers are stored.