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.
1import java.util.*;
2
3class Solution {
4 public String fractionAddition(String expression) {
5 int numerator = 0, denominator = 1, n, d;
6 int sign = 1, i = 0;
7
8 while (i < expression.length()) {
9 sign = (expression.charAt(i) == '-') ? -1 : 1;
10 if (expression.charAt(i) == '-' || expression.charAt(i) == '+') i++;
11
12 int j = i;
13 while (expression.charAt(j) != '/') j++;
14 n = Integer.parseInt(expression.substring(i, j)) * sign;
15 i = ++j;
16 while (j < expression.length() && Character.isDigit(expression.charAt(j))) j++;
17 d = Integer.parseInt(expression.substring(i, j));
18 i = j;
19
20 int lcmDen = denominator * (d / gcd(denominator, d));
21 numerator = numerator * (lcmDen / denominator) + n * (lcmDen / d);
22 denominator = lcmDen;
23 }
24
25 int gcd = gcd(Math.abs(numerator), denominator);
26 numerator /= gcd;
27 denominator /= gcd;
28
29 return numerator + "/" + denominator;
30 }
31
32 private int gcd(int a, int b) {
33 return b == 0 ? a : gcd(b, a % b);
34 }
35}This Java implementation makes use of String manipulation functions to parse each fraction within the expression. A mutual denominator is calculated using LCM for addition or subtraction and result is simplified by GCD to form the final output.
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 JavaScript implementation operates by processing the expression into meaningful fractions, maintains running calculations for the updated total, and utilizes LCM for operations on fractional pieces.