The "Equal Rational Numbers" problem requires you to determine whether two strings, S and T, each representing a rational number, are numerically equal. These strings can represent numbers in the form of decimals, and may include repeating decimals using parentheses. For example, "0.(52)" means 0.52525252... and "0.5(25)" means 0.52525252... as well.
Your task is to write a function that returns True if the two numbers represented by S and T are equal, and False otherwise.
S and T are non-empty strings.
At first glance, it might seem that simply converting the strings to floating-point numbers and comparing them should work. However, this approach fails for repeating decimals, since floating-point representations are not exact for infinite decimals. For instance, "0.(9)" is mathematically equal to "1.0", but their floating-point representations may not match exactly.
The naive brute-force approach would be to expand both decimals to a certain length and then compare, but this is inefficient and may not always be accurate due to precision issues. Instead, we need a way to convert both numbers to a canonical (standardized) form, such as a fraction (numerator/denominator), so that both can be compared exactly.
The key insight is to parse the string, extract the integer, non-repeating, and repeating parts, and then compute the exact fraction that the decimal represents. Once both numbers are in fraction form, we can simply compare their numerators and denominators after reducing them.
The solution involves parsing the string representation of each rational number and converting it to its exact fractional form. Here are the steps:
x = integer_part.non_repeating(repeating).n be the length of non-repeating part, r the length of repeating part.
value = integer_part + non_repeating / 10^n + repeating / (10^n * (10^r - 1))
This method ensures exact comparison, avoiding floating-point inaccuracies and handling repeating decimals correctly.
Let's walk through the example with S = "0.(52)" and T = "0.5(25)".
The "Equal Rational Numbers" problem is best solved by converting each string representation into its exact fractional form, rather than relying on floating-point arithmetic or brute-force expansion. By parsing the integer, non-repeating, and repeating parts, and applying the formula for converting repeating decimals to fractions, we can reduce the problem to comparing two fractions. This approach is both efficient and precise, handling all edge cases and ensuring correctness.
import math
def isRationalEqual(S: str, T: str) -> bool:
def to_fraction(s):
if '(' in s:
nonrep, rep = s.split('(')
rep = rep.rstrip(')')
else:
nonrep, rep = s, ''
if '.' in nonrep:
int_part, dec_part = nonrep.split('.')
else:
int_part, dec_part = nonrep, ''
int_part = int(int_part) if int_part else 0
dec_part = dec_part if dec_part else ''
# If no repeating part
if not rep:
if not dec_part:
return (int_part, 1)
numerator = int(str(int_part) + dec_part) if int_part != 0 else int(dec_part)
denominator = 10 ** len(dec_part)
return (numerator, denominator)
# There is a repeating part
n = len(dec_part)
r = len(rep)
base = int(str(int_part) + dec_part) if dec_part else int_part
# numerator = [all decimal digits incl. repeating] - [just non-repeating]
full = dec_part + rep
num_full = int(full) if full else 0
num_nonrep = int(dec_part) if dec_part else 0
numerator = int_part * (10 ** (n + r) - 10 ** n) + num_full - num_nonrep
denominator = 10 ** n * (10 ** r - 1)
# If integer part is 0, numerator is just num_full - num_nonrep
if int_part == 0:
numerator = num_full - num_nonrep
gcd = math.gcd(numerator, denominator)
return (numerator // gcd, denominator // gcd)
n1, d1 = to_fraction(S)
n2, d2 = to_fraction(T)
return n1 * d2 == n2 * d1
#include <string>
#include <numeric>
using namespace std;
class Solution {
public:
pair<long long, long long> toFraction(string s) {
string nonrep, rep;
auto pos = s.find('(');
if (pos != string::npos) {
nonrep = s.substr(0, pos);
rep = s.substr(pos + 1, s.size() - pos - 2);
} else {
nonrep = s;
rep = "";
}
string int_part, dec_part;
auto dot = nonrep.find('.');
if (dot != string::npos) {
int_part = nonrep.substr(0, dot);
dec_part = nonrep.substr(dot + 1);
} else {
int_part = nonrep;
dec_part = "";
}
long long intp = int_part.empty() ? 0 : stoll(int_part);
// No repeating
if (rep.empty()) {
if (dec_part.empty())
return {intp, 1};
long long numerator = intp * pow10(dec_part.length()) + (dec_part.empty() ? 0 : stoll(dec_part));
long long denominator = pow10(dec_part.length());
long long g = gcd(numerator, denominator);
return {numerator / g, denominator / g};
}
int n = dec_part.length(), r = rep.length();
string full = dec_part + rep;
long long num_full = full.empty() ? 0 : stoll(full);
long long num_nonrep = dec_part.empty() ? 0 : stoll(dec_part);
long long numerator = intp * (pow10(n + r) - pow10(n)) + num_full - num_nonrep;
long long denominator = pow10(n) * (pow10(r) - 1);
if (intp == 0)
numerator = num_full - num_nonrep;
long long g = gcd(numerator, denominator);
return {numerator / g, denominator / g};
}
int pow10(int n) {
int res = 1;
while (n--) res *= 10;
return res;
}
bool isRationalEqual(string S, string T) {
auto f1 = toFraction(S);
auto f2 = toFraction(T);
return f1.first * f2.second == f2.first * f1.second;
}
};
class Solution {
public boolean isRationalEqual(String S, String T) {
int[] f1 = toFraction(S);
int[] f2 = toFraction(T);
return f1[0] * f2[1] == f2[0] * f1[1];
}
private int[] toFraction(String s) {
String nonrep, rep;
int l = s.indexOf('(');
if (l != -1) {
nonrep = s.substring(0, l);
rep = s.substring(l + 1, s.length() - 1);
} else {
nonrep = s;
rep = "";
}
String[] parts = nonrep.split("\\.");
String intPart = parts[0];
String decPart = parts.length > 1 ? parts[1] : "";
int intp = intPart.isEmpty() ? 0 : Integer.parseInt(intPart);
if (rep.isEmpty()) {
if (decPart.isEmpty())
return new int[]{intp, 1};
int numerator = intp * pow10(decPart.length()) + (decPart.isEmpty() ? 0 : Integer.parseInt(decPart));
int denominator = pow10(decPart.length());
int g = gcd(numerator, denominator);
return new int[]{numerator / g, denominator / g};
}
int n = decPart.length(), r = rep.length();
String full = decPart + rep;
int numFull = full.isEmpty() ? 0 : Integer.parseInt(full);
int numNonRep = decPart.isEmpty() ? 0 : Integer.parseInt(decPart);
int numerator = intp * (pow10(n + r) - pow10(n)) + numFull - numNonRep;
int denominator = pow10(n) * (pow10(r) - 1);
if (intp == 0)
numerator = numFull - numNonRep;
int g = gcd(numerator, denominator);
return new int[]{numerator / g, denominator / g};
}
private int pow10(int n) {
int res = 1;
while (n-- > 0) res *= 10;
return res;
}
private int gcd(int a, int b) {
while (b != 0) {
int t = a % b;
a = b;
b = t;
}
return a;
}
}
function isRationalEqual(S, T) {
function toFraction(s) {
let nonrep, rep;
let l = s.indexOf('(');
if (l !== -1) {
nonrep = s.substring(0, l);
rep = s.substring(l + 1, s.length - 1);
} else {
nonrep = s;
rep = '';
}
let intPart, decPart;
let dot = nonrep.indexOf('.');
if (dot !== -1) {
intPart = nonrep.substring(0, dot);
decPart = nonrep.substring(dot + 1);
} else {
intPart = nonrep;
decPart = '';
}
let intp = intPart ? parseInt(intPart) : 0;
if (!rep) {
if (!decPart)
return [intp, 1];
let numerator = intp * Math.pow(10, decPart.length) + (decPart ? parseInt(decPart) : 0);
let denominator = Math.pow(10, decPart.length);
let g = gcd(numerator, denominator);
return [numerator / g, denominator / g];
}
let n = decPart.length, r = rep.length;
let full = decPart + rep;
let numFull = full ? parseInt(full) : 0;
let numNonRep = decPart ? parseInt(decPart) : 0;
let numerator = intp * (Math.pow(10, n + r) - Math.pow(10, n)) + numFull - numNonRep;
let denominator = Math.pow(10, n) * (Math.pow(10, r) - 1);
if (intp === 0)
numerator = numFull - numNonRep;
let g = gcd(numerator, denominator);
return [numerator / g, denominator / g];
}
function gcd(a, b) {
while (b !== 0) {
let t = a % b;
a = b;
b = t;
}
return a;
}
let [n1, d1] = toFraction(S);
let [n2, d2] = toFraction(T);
return n1 * d2 === n2 * d1;
}