Fraction Addition and Subtraction

Leetcode Problem:

• Fraction Addition and Subtraction

Summary

• Given a string representing an expression of fraction addition and subtraction, return the calculation result in string format.

Approach

• The solution uses an istringstream to parse the input string and then applies the Euclidean algorithm to find the greatest common divisor of the numerator and denominator of each fraction, reducing them to their simplest form
• The final result is then converted to a string and returned.

Complexity

• O(n), where n is the number of fractions in the input string

Explain

• The solution works by iterating over each fraction in the input string, applying the Euclidean algorithm to reduce the fraction to its simplest form
• The final result is then converted to a string and returned
• The time complexity of the solution is O(n), where n is the number of fractions in the input string, because each fraction is processed once and the operations involved in the Euclidean algorithm take constant time.

Solution Code:

class Solution {
public:
    string fractionAddition(string expression) {
    istringstream in(expression);
    int A = 0, B = 1, a, b;
    char _;
    while (in >> a >> _ >> b) {
        A = A * b + a * B;
        B *= b;
        int g = abs(__gcd(A, B));
        A /= g;
        B /= g;
    }
    return to_string(A) + '/' + to_string(B);
}
};