Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/972.html
972. Equal Rational Numbers
Level
Hard
Description
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 <= 40 <= <NonRepeatingPart>.length <= 41 <= <RepeatingPart>.length <= 4
Solution
For both strings S and T, convert each number into a rational number, which contains a numerator and a denominator.
To convert a string to a rational number, consider the following cases.
-
The string only contains the integer part. If the decimal point exists, remove the decimal point. Set the numerator to be the integer part and the denominator to be 1. For example, 12 is represented as 12/1.
-
The string represents a decimal with no repeating parts. For example, 2.12 has an integer part 2 and a decimal part 0.12. The decimal part can be represented as 12/100, and the result of fraction reduction is 3/25. Adding the integer part to the rational number and the result is 53/25.
-
The string represents a repeating decimal. Consider the following two cases. 3.1. Only the repeating part exists. For example, 1.(142857) has an integer part 1 and a decimal part 0.(142857), The decimal part can be represented as 142857/999999, and the result of fraction reduction is 1/7. Adding the integer part to the rational number and the result is 8/7. 3.2 Both the non-repeating part and the repeating part exist. For example, 3.1(3) has an integer part 3 and a decimal part 0.1(3). The decimal part can be represented by (13-1)/90 = 12/90, and the result of fraction reduction is 2/15. Adding the integer part to the rational number and the result is 47/15.
After converting both strings to rational numbers, check whether the two rational numbers’ numerators are the same and denominators are the same.
-
class Solution { public boolean isRationalEqual(String S, String T) { int[] rationalS = getRational(S); int[] rationalT = getRational(T); return rationalS[0] == rationalT[0] && rationalS[1] == rationalT[1]; } public int[] getRational(String str) { boolean positive = true; if (str.charAt(0) == '-') { str = str.substring(1); positive = false; } int dotIndex = str.indexOf('.'); if (dotIndex < 0) { int integer = Integer.parseInt(str); if (!positive) integer = -integer; int[] rational = {integer, 1}; return rational; } int length = str.length(); if (dotIndex == length - 1) { int integer = Integer.parseInt(str.substring(0, dotIndex)); if (!positive) integer = -integer; int[] rational = {integer, 1}; return rational; } String integerPart = str.substring(0, dotIndex); int integer = Integer.parseInt(integerPart); String decimalPart = str.substring(dotIndex + 1); int decimalPartLength = length - dotIndex - 1; int repeatingIndex = str.indexOf('('); if (repeatingIndex < 0) { int numerator = Integer.parseInt(decimalPart); int denominator = (int) Math.pow(10, decimalPartLength); int gcd = gcd(numerator, denominator); numerator /= gcd; denominator /= gcd; int[] rational = {numerator, denominator}; rational[0] += integer * denominator; if (!positive) rational[0] = -rational[0]; return rational; } else { if (repeatingIndex - dotIndex == 1) { int numerator = Integer.parseInt(str.substring(repeatingIndex + 1, length - 1)); int denominator = (int) Math.pow(10, decimalPartLength - 2) - 1; int gcd = gcd(numerator, denominator); numerator /= gcd; denominator /= gcd; int[] rational = {numerator, denominator}; rational[0] += integer * denominator; if (!positive) rational[0] = -rational[0]; return rational; } else { int nonRepeatingLength = repeatingIndex - dotIndex - 1; int repeatingLength = length - 2 - repeatingIndex; int nonRepeating = Integer.parseInt(str.substring(dotIndex + 1, repeatingIndex)); int numerator = nonRepeating * (int) Math.pow(10, repeatingLength) + Integer.parseInt(str.substring(repeatingIndex + 1, length - 1)) - nonRepeating; int denominator = (int) (Math.pow(10, repeatingLength) - 1) * (int) (Math.pow(10, nonRepeatingLength)); int gcd = gcd(numerator, denominator); numerator /= gcd; denominator /= gcd; int[] rational = {numerator, denominator}; rational[0] += integer * denominator; if (!positive) rational[0] = -rational[0]; return rational; } } } public int gcd(int a, int b) { if (a == 0 && b == 0) return 1; while (a > 0 && b > 0) { if (a > b) { int temp = a; a = b; b = temp; } b %= a; } return a == 0 ? b : a; } } -
// OJ: https://leetcode.com/problems/equal-rational-numbers/ // Time: O(1) // Space: O(1) struct Number { string prefix, repeat; Number(string p, string r) : prefix(p), repeat(r) { int N = r.size(), len = 1; // find the minimal repeat part for (; len <= N / 2; ++len) { int i = 0; while (i < N && repeat[i] == repeat[i % len]) ++i; if (i == N) break; } if (len <= N / 2) repeat = repeat.substr(0, len); if (repeat == "0") repeat = ""; normalizePrefix(); } void normalizePrefix() { if (prefix.find_first_of(".") == string::npos) { prefix += '.'; } else if (repeat.empty()) { // only pop trailing zeroes if repeat is empty while (prefix.back() == '0') prefix.pop_back(); } } }; class Solution { string increment(string &s) { int i = s.size() - 1, carry = 1; for (; i >= 0 && carry; --i) { if (s[i] == '.') continue; carry += s[i] - '0'; s[i] = '0' + carry % 10; carry /= 10; } if (carry) s.insert(begin(s), '1'); return s; } Number getNumber(string &s) { auto i = s.find_first_of("("); if (i == string::npos) return Number(s, ""); auto ans = Number(s.substr(0, i), s.substr(i + 1, s.size() - i - 2)); if (ans.repeat == "9") { ans.repeat = ""; ans.prefix = increment(ans.prefix); ans.normalizePrefix(); } return ans; } public: bool isRationalEqual(string s, string t) { auto a = getNumber(s), b = getNumber(t); if (a.repeat.size() != b.repeat.size()) return false; if (a.repeat.size() == 0) return a.prefix == b.prefix; if (a.prefix.size() > b.prefix.size()) swap(a, b); int i = 0, N = b.prefix.size(); for (; i < N; ++i) { if (i < a.prefix.size()) { if (a.prefix[i] != b.prefix[i]) return false; } else { if (a.repeat[(i - a.prefix.size()) % a.repeat.size()] != b.prefix[i]) return false; } } i = (i - a.prefix.size()) % a.repeat.size(); return a.repeat.substr(i) + a.repeat.substr(0, i) == b.repeat; } }; -
# 972. Equal Rational Numbers # https://leetcode.com/problems/equal-rational-numbers/ class Solution: def isRationalEqual(self, s: str, t: str) -> bool: def g(s): s2 = "" rep1 = "" ok = False for x in s: if x == "(" or x == ")": ok = True continue if ok: rep1 += x else: s2 += x return (s2, rep1) os1, rep1 = g(s) os2, rep2 = g(t) s1 = os1 + rep1 * 30 s2 = os2 + rep2 * 30 if len(rep1) == 0 and len(rep2) == 0: return s1 == s2 or float(s1) == float(s2) if s1 == s2 or float(s1) == float(s2): return True def good(s1, s2): count = 1 curr = s1[-1] roundCount = len(s2) - 2 for i in range(len(s1) - 2, -1, -1): if curr == s1[i]: count += 1 else: return False if i > 0 and s1[i] != s1[i - 1] and count >= 30: ss = s1[:i + 1] r = float(ss) + float("0." + "0" * (len(ss) - 3 - bool(s1[i - 1] == ".")) + "1") if r == float(s2): return True return False return good(s1, s2) or good(s2, s1)