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 <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5int gcd(int a, int b) {
6 while (b != 0) {
7 int t = b;
8 b = a % b;
9 a = t;
10 }
11 return a;
12}
13
14int lcm(int a, int b) {
15 return (a / gcd(a, b)) * b;
16}
17
18char* fractionAddition(char* expression) {
19 int numerator = 0, denominator = 1, n, d;
20 char sign, *ptr = expression;
21 while (*ptr) {
22 n = (*ptr == '-' || *ptr == '+') ? atoi(ptr) : 1;
23 sign = (*ptr == '-') ? '-' : '+';
24 ptr += (n == 1 ? 0 : (sign == '-' ? 1 : 2));
25 d = atoi(strchr(ptr, '/') + 1);
26 ptr = strchr(ptr, '/') + 1;
27 ptr += (*ptr == '-') ? 1 : 0;
28
29 int commonDen = lcm(denominator, d);
30 numerator = numerator * (commonDen / denominator) + n * (commonDen / d);
31 denominator = commonDen;
32 }
33
34 int commonDiv = gcd(abs(numerator), denominator);
35 numerator /= commonDiv;
36 denominator /= commonDiv;
37
38 char *result = (char *)malloc(32);
39 sprintf(result, "%d/%d", numerator, denominator);
40 return result;
41}We loop through each fraction in the expression, calculate the LCM of the current denominator and the one in the expression, adjust numerators accordingly, and perform the addition or subtraction. Finally, the result is simplified by dividing it by the GCD of the numerator and denominator.
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.
1from
The Python function consolidates fractions by iterating through expression and maintaining a cumulative numerator and denominator, dynamically calculating the result for progressively encountered fractions.