972. Equal Rational Numbers
e.g. 0.(123)
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.
In general a rational number can be represented using up to three parts: an integer part, a non-repeating part, and a repeating part. The number will be represented in one of the following three ways:
<IntegerPart>
(e.g. 0, 12, 123)<IntegerPart><.><NonRepeatingPart>
(e.g. 0.5, 1., 2.12, 2.0001)<IntegerPart><.><NonRepeatingPart><(><RepeatingPart><)>
(e.g. 0.1(6), 0.9(9), 0.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)
Both 0.1(6) or 0.1666(6) or 0.166(66) are correct representations of 1 / 6.
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) = "".
Note:
- Each part consists only of digits.
- The
<IntegerPart>
will not begin with 2 or more zeros. (There is no other restriction on the digits of each part.) 1 <= <IntegerPart>.length <= 4
0 <= <NonRepeatingPart>.length <= 4
1 <= <RepeatingPart>.length <= 4
Solution by neal_wu (Rank #1) in contest (Very elegant solution!)
Idea:
Idea:
- Represent the number in "irreducible fraction" form
- a and b can exceed 32-bit integer, so use 64-bit integer to store a and b
- Fraction can naturally represent repeat part
struct fraction {
int64_t numer, denom;
void reduce() {
int64_t g = __gcd(numer, denom);
numer /= g;
denom /= g;
}
bool operator==(const fraction &other) const {
return numer == other.numer && denom == other.denom;
}
};
int64_t power10(int n) {
return n == 0 ? 1 : 10 * power10(n - 1);
}
fraction to_fraction(string S) {
size_t period = S.find('.');
if (period == string::npos)
return {stoll(S), 1};
int64_t integer = stoll(S.substr(0, period));
S = S.substr(period + 1);
if (S.empty())
return {integer, 1};
size_t paren = S.find('(');
if (paren == string::npos) {
int n = S.size();
int64_t p = power10(n);
return {integer * p + stoll(S), p};
}
int64_t p = power10(paren);
int64_t nonrepeating = paren == 0 ? 0 : stoll(S.substr(0, paren));
string remaining = S.substr(paren + 1, S.size() - 1 - (paren + 1));
int64_t rp = power10(remaining.size()) - 1;
Why rp = power10(remaining.size()) - 1? Because the repeating part is calculated by geometric series,e.g. 0.(123)
int64_t repeating = stoll(remaining);
return {integer * p * rp + nonrepeating * rp + repeating, p * rp};
}
class Solution {
public:
bool isRationalEqual(string S, string T) {
fraction A = to_fraction(S);
fraction B = to_fraction(T);
A.reduce();
B.reduce();
return A == B;
}
};
No comments:
Post a Comment