Sponsored
Sponsored
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 <iostream>
2#include <string>
3#include <cmath>
4
5long long gcd(long long a, long long b) {
6 return b == 0 ? a : gcd(b, a % b);
7}
8
9void splitNumber(const std::string &s, long long &intPart, long long &nonRepeat, long long &repeat, int &nonRepeatLen, int &repeatLen) {
10 intPart = 0;
11 nonRepeat = 0;
12 repeat = 0;
13 nonRepeatLen = 0;
14 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;
}
The C++ solution follows a similar procedure to the C solution with object-oriented features and the std::string class for easier management of strings. It uses std::pow for calculations of powers of 10 and performs the conversion and reduction of fractions for 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.
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.
1function expandDecimal(s, precision
The JavaScript implementation mirrors the Python logic, using strings and loops to assemble a representation of the expanded decimal up to the predefined acceptable precision. It then compares the results directly.