592. Fraction Addition and Subtraction

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

The final result should be an irreducible fraction. If your final result is an integer, change it to the format of a fraction that has a denominator 1. So in this case, 2 should be converted to 2/1.

Example 1:

Input: expression = "-1/2+1/2"
Output: "0/1"

Example 2:

Input: expression = "-1/2+1/2+1/3"
Output: "1/3"

Example 3:

Input: expression = "1/3-1/2"
Output: "-1/6"

Constraints:

• The input string only contains '0' to '9', '/', '+' and '-'. So does the output.
• Each fraction (input and output) has the format ±numerator/denominator. If the first input fraction or the output is positive, then '+' will be omitted.
• The input only contains valid irreducible fractions, where the numerator and denominator of each fraction will always be in the range [1, 10]. If the denominator is 1, it means this fraction is actually an integer in a fraction format defined above.
• The number of given fractions will be in the range [1, 10].
• The numerator and denominator of the final result are guaranteed to be valid and in the range of 32-bit int.

Approach 01:

#include <string>
#include <sstream>
#include <cmath>
#include <numeric> // for std::gcd

class Solution {
public:
    std::string fractionAddition(std::string expression) {
        int accumulatedNumerator = 0;
        int accumulatedDenominator = 1;
        
        std::istringstream input(expression);
        char separator;
        int numerator, denominator;
        
        while (input >> numerator >> separator >> denominator) {
            accumulatedNumerator = accumulatedNumerator * denominator + numerator * accumulatedDenominator;
            accumulatedDenominator *= denominator;
            
            int commonDivisor = std::abs(std::gcd(accumulatedNumerator, accumulatedDenominator));
            accumulatedNumerator /= commonDivisor;
            accumulatedDenominator /= commonDivisor;
        }
        
        return std::to_string(accumulatedNumerator) + "/" + std::to_string(accumulatedDenominator);
    }
};

from math import gcd

class Solution:
    def fractionAddition(self, expression: str) -> str:
        accumulatedNumerator = 0
        accumulatedDenominator = 1
        
        index = 0
        while index < len(expression):
            sign = 1
            if expression[index] == '-' or expression[index] == '+':
                if expression[index] == '-':
                    sign = -1
                index += 1

            numerator = 0
            while index < len(expression) and expression[index].isdigit():
                numerator = numerator * 10 + int(expression[index])
                index += 1
            numerator *= sign
            index += 1  # Skip the '/'
            denominator = 0
            while index < len(expression) and expression[index].isdigit():
                denominator = denominator * 10 + int(expression[index])
                index += 1
            
            # Calculate new accumulated fraction
            accumulatedNumerator = accumulatedNumerator * denominator + numerator * accumulatedDenominator
            accumulatedDenominator *= denominator
            
            # Simplify the fraction by the greatest common divisor
            commonDivisor = abs(gcd(accumulatedNumerator, accumulatedDenominator))
            accumulatedNumerator //= commonDivisor
            accumulatedDenominator //= commonDivisor

        return f"{accumulatedNumerator}/{accumulatedDenominator}"

Time Complexity

• Parsing the Expression:

  The function iterates through the input string to parse each fraction. Assuming the expression has \( n \) fractions, this step takes \( O(n) \) time.

• Updating the Accumulated Fraction:

  For each fraction, the function performs arithmetic operations, including finding the greatest common divisor (GCD). Computing the GCD using the Euclidean algorithm takes \( O(\log(\min(\text{numerator}, \text{denominator}))) \). Thus, for \( n \) fractions, this step takes \( O(n \cdot \log D) \), where \( D \) is the maximum denominator.

• Overall Time Complexity:

  The overall time complexity is \( O(n \cdot \log D) \), where \( n \) is the number of fractions, and \( D \) is the maximum denominator.

Space Complexity

• Auxiliary Space:

  The function uses a constant amount of extra space for variables such as accumulatedNumerator, accumulatedDenominator, and the input stream input.

• Overall Space Complexity:

  The overall space complexity is \( O(1) \) since the space used does not depend on the size of the input.