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.
1using System;
2
3public class Solution {
4 public string FractionAddition(string expression) {
5 int numerator = 0, denominator = 1, num, dem;
6 int sign = 1;
7 for (int i = 0; i < expression.Length; ) {
8 if (expression[i] == '-' || expression[i] == '+') {
9 sign = expression[i] == '-' ? -1 : 1;
10 i++;
11 }
12 int start = i;
13 while (expression[i] != '/') i++;
14 num = int.Parse(expression.Substring(start, i - start)) * sign;
15 i++;
16 start = i;
17 while (i < expression.Length && Char.IsDigit(expression[i])) i++;
18 dem = int.Parse(expression.Substring(start, i - start));
19
20 int lcmDen = denominator * (dem / GCD(denominator, dem));
21 numerator = numerator * (lcmDen / denominator) + num * (lcmDen / dem);
22 denominator = lcmDen;
23 }
24
25 int gcd = GCD(Math.Abs(numerator), denominator);
26 numerator /= gcd;
27 denominator /= gcd;
28 return numerator + "/" + denominator;
29 }
30
31 private int GCD(int a, int b) {
32 return b == 0 ? a : GCD(b, a % b);
33 }
34}
C# uses string operations for parsing as well, translating each fraction to a common denominator followed by adjustments in numerators, using LCM for calculations. The output downscales to irreducible form using GCD before creating the final result 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
public class Solution {
public string FractionAdditionConsec(string expression) {
int num = 0, den = 1, n, d;
int i = 0, sign = 1;
while (i < expression.Length) {
if (expression[i] == '+' || expression[i] == '-') {
sign = (expression[i] == '-') ? -1 : 1;
i++;
}
int numBegin = i;
while (expression[i] != '/') i++;
n = int.Parse(expression.Substring(numBegin, i - numBegin));
n *= sign;
i++;
int dBegin = i;
while (i < expression.Length && Expression[i] >= '0' && expression[i] <= '9') i++;
d = int.Parse(expression.Substring(dBegin, i - dBegin));
int lcmDenom = den * (d / GCD(den, d));
num = num * (lcmDenom / den) + n * (lcmDenom / d);
den = lcmDenom;
}
int gcd = GCD(Math.Abs(num), den);
return (num / gcd) + "/" + (den / gcd);
}
private int GCD(int a, int b) {
return b == 0 ? a : GCD(b, a % b);
}
}
The C# solution involves parsing each section for proper collection and integration into the running fraction amounts by making use of GCD and LCM to continuously adjust denominator and numerator for seamless concatenation.