Sponsored
Sponsored
This approach involves using the Least Common Multiple (LCM) to find a common denominator for all fractions. Then, add or subtract the numerators accordingly, and finally, simplify the resulting fraction.
Time Complexity: O(n), where n is the length of the expression.
Space Complexity: O(1), as we only use a fixed amount of additional space for variables.
1from math import gcd
2
3def fractionAddition(expression: str) -> str:
4 def lcm(a, b):
5 return a * b // gcd(a, b)
6
7 num, denom = 0, 1
8 i, n = 0, len(expression)
9
10 while i < n:
11 sign = 1
12 if expression[i] in '+-':
13 sign = -1 if expression[i] == '-' else 1
14 i += 1
15 j = i
16 while expression[j] != '/':
17 j += 1
18 num1 = int(expression[i:j]) * sign
19 i = j + 1
20 j = i
21 while j < n and expression[j].isdigit():
22 j += 1
23 denom1 = int(expression[i:j])
24 i = j
25
26 common_denom = lcm(denom, denom1)
27 num = num * (common_denom // denom) + num1 * (common_denom // denom1)
28 denom = common_denom
29
30 gcd_ = gcd(abs(num), denom)
31 return f"{num // gcd_}/{denom // gcd_}"The Python function is simple and concise - it utilizes helper functions like gcd and lcm to compute and combine fractions. Parsing and computation lead to a final simplification and output in irreducible form.
In this method, we handle each fraction consecutively, updating the numerator and denominator dynamically. This maintains an accumulated result for fractions encountered sequentially.
Time Complexity: O(n) with direct proportionality to length.
Space Complexity: O(1) as with minimum additional memory usage constant.
1
The Python function consolidates fractions by iterating through expression and maintaining a cumulative numerator and denominator, dynamically calculating the result for progressively encountered fractions.