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.
1function gcd(a, b) {
2 return b === 0 ? a : gcd(b, a % b);
3}
4
5function fractionAddition(expression) {
6 const lcm = (a, b) => a * b / gcd(a, b);
7
8 let num = 0, den = 1, i = 0, n = expression.length;
9 while (i < n) {
10 let sign = 1;
11 if (expression[i] === '-' || expression[i] === '+') {
12 sign = expression[i] === '-' ? -1 : 1;
13 i++;
14 }
15
16 let numStart = i;
17 while (expression[i] !== '/') i++;
18 let numerator = parseInt(expression.slice(numStart, i)) * sign;
19 i++;
20 let denomStart = i;
21 while (i < n && !isNaN(parseInt(expression[i]))) i++;
22 let denominator = parseInt(expression.slice(denomStart, i));
23
24 const lcmDenom = lcm(den, denominator);
25 num = num * (lcmDenom / den) + numerator * (lcmDenom / denominator);
26 den = lcmDenom;
27 }
28
29 const commonDiv = gcd(Math.abs(num), den);
30 return `${num / commonDiv}/${den / commonDiv}`;
31}JavaScript approach entails splitting the expression to translate and deal with fractions in line with arithmetic and common denominator calculations. The end result outputs the irreducible fraction 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
The Java solution consists of traversing characters while dynamically altering the ongoing total by leveraging the accumulated LCM denominators to consolidate fractions as they appear.