Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/592.html # 592. Fraction Addition and Subtraction
Level
Medium
Description
Given a string representing an expression of fraction addition and subtraction, you need to return the calculation result in string format. The final result should be irreducible fraction. If your final result is an integer, say 2, you need to change it to the format of fraction that has denominator 1. So in this case, 2 should be converted to 2/1.
Example 1:
Input:“-1/2+1/2”
Output: “0/1”
Example 2:
Input:“-1/2+1/2+1/3”
Output: “1/3”
Example 3:
Input:“1/3-1/2”
Output: “-1/6”
Example 4:
Input:“5/3+1/3”
Output: “2/1”
Note:
- The input string only contains
'0'to'9','/','+'and'-'. So does the output. - Each fraction (input and output) has format
±numerator/denominator. If the first input fraction or the output is positive, then'+'will be omitted. - The input only contains valid irreducible fractions, where the numerator and denominator of each fraction will always be in the range [1,10]. If the denominator is 1, it means this fraction is actually an integer in a fraction format defined above.
- The number of given fractions will be in the range [1,10].
- The numerator and denominator of the final result are guaranteed to be valid and in the range of 32-bit int.
Solution
This solution creates a class called Rational, which contains two data fields, numerator and denominator, and supports addition and subtraction.
Split the terms of fractions. Replace all occurrences of “-“ with “+-“, but remove the “+” at the beginning of the expression. Then split the expression using “+” to get an array that contains the separated terms.
Initially, the sum of all the fractions is 0.
For each term in the array, create an object of Rational type, which is a rational number, and add the rational number to the sum, using the methods defined in class Rational.
After the sum of all fractions is obtained, convert the sum into a string of fraction, and return the string.
-
class Solution { public String fractionAddition(String expression) { expression = expression.replaceAll("-", "+-"); if (expression.charAt(0) == '+') expression = expression.substring(1); String[] array = expression.split("\\+"); Rational sum = new Rational(0); int length = array.length; for (int i = 0; i < length; i++) { String rationalStr = array[i]; int divisionIndex = rationalStr.indexOf('/'); if (divisionIndex < 0) { Rational rational = new Rational(Long.parseLong(rationalStr)); sum = sum.add(rational); } else { long numerator = Long.parseLong(rationalStr.substring(0, divisionIndex)); long denominator = Long.parseLong(rationalStr.substring(divisionIndex + 1)); Rational rational = new Rational(numerator, denominator); sum = sum.add(rational); } } String sumStr = sum.numerator + "/" + sum.denominator; return sumStr; } } class Rational { long numerator = 0; long denominator = 1; public Rational() { } public Rational(long numerator) { this(numerator, 1); } public Rational(long numerator, long denominator) { long gcd = gcd(numerator, denominator); if (denominator < 0) { numerator = -numerator; denominator = -denominator; } this.numerator = numerator / gcd; this.denominator = denominator / gcd; } public Rational add(Rational rational2) { long newNumerator = this.numerator * rational2.denominator + rational2.numerator * this.denominator; long newDenominator = this.denominator * rational2.denominator; return new Rational(newNumerator, newDenominator); } public Rational subtract(Rational rational2) { long newNumerator = this.numerator * rational2.denominator - rational2.numerator * this.denominator; long newDenominator = this.denominator * rational2.denominator; return new Rational(newNumerator, newDenominator); } public long gcd(long a, long b) { a = Math.abs(a); b = Math.abs(b); if (a == 0 && b == 0) return 1; while (a != 0 && b != 0) { if (a > b) { long temp = a; a = b; b = temp; } b %= a; } return a == 0 ? b : a; } } -
// OJ: https://leetcode.com/problems/fraction-addition-and-subtraction/ // Time: O(N) // Space: O(N) class Solution { public: string fractionAddition(string s) { vector<array<int, 2>> frac; int lcm = 1; // least common multiple for (int i = 0, N = s.size(); i < N;) { bool neg = s[i] == '-'; if (s[i] == '-' || s[i] == '+') ++i; int num = 0, den = 0; while (isdigit(s[i])) num = num * 10 + (s[i++] - '0'); if (neg) num *= -1; ++i; // '/' while (i < N && isdigit(s[i])) den = den * 10 + (s[i++] - '0'); int d = gcd(lcm, den); lcm = lcm * den / d; frac.push_back({ num, den }); } int num = 0; for (auto &f : frac) num += f[0] * (lcm / f[1]); int d = gcd(num, lcm); return to_string(num / d) + "/" + to_string(lcm / d); } }; -
class Solution: def fractionAddition(self, expression: str) -> str: x, y = 0, 6 * 7 * 8 * 9 * 10 if expression[0].isdigit(): expression = '+' + expression i, n = 0, len(expression) while i < n: sign = -1 if expression[i] == '-' else 1 i += 1 j = i while j < n and expression[j] not in '+-': j += 1 s = expression[i:j] a, b = s.split('/') x += sign * int(a) * y // int(b) i = j z = gcd(x, y) x //= z y //= z return f'{x}/{y}' ############ class Solution(object): def fractionAddition(self, expression): """ :type expression: str :rtype: str """ def add(a, b): if a == "0/1": return b def gcd(a, b): while b != 0: a, b = b, a % b return a (an, ad), (bn, bd) = map(int, a.split("/")), map(int, b.split("/")) lcm = (ad * bd) / (gcd(ad, bd)) an, bn = an * (lcm / ad), bn * (lcm / bd) n = an + bn g = gcd(n, lcm) return str(n / g) + "/" + str(lcm / g) expression += "+" ans = "0/1" start = 0 for i in range(1, len(expression)): if expression[i] in ["+", "-"]: num = expression[start:i] ans = add(ans, num) start = i return ans if ans[0] != "+" else ans[1:]