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.
1#include <iostream>
2#include <sstream>
3#include <numeric>
4using namespace std;
5
6string fractionAddition(string expression) {
7 istringstream is(expression);
8 int num = 0, den = 1, n, d;
9 char slash, op = '+';
10 while (is >> n >> slash >> d) {
11 int common_den = den / gcd(den, d) * d;
12 num = num * (common_den / den) + (op == '+' ? 1 : -1) * n * (common_den / d);
13 den = common_den;
14 op = is.peek();
15 if (op == '+' || op == '-')
16 is.get();
17 }
18 int gcd_ = abs(gcd(num, den));
19 return to_string(num / gcd_) + '/' + to_string(den / gcd_);
20}Using istringstream to parse the input expression, the approach involves finding the LCM of denominators for each fraction and translating numerators according to the common denominator followed by addition or subtraction based on the operator present. Result is then simplified using GCD before forming the output string.
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
This solution parses through the expression while employing a dynamic running total, adjusting numerically with current fractions, computing the least common multiple in simultaneous manner.