We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Fraction Addition and Subtraction

Difficulty: Medium

Problem Description

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.

Key Insights

  • The expression consists of fractions that can be positive or negative.
  • Each fraction has the format ±numerator/denominator.
  • The output must be in the irreducible form.
  • The input only contains valid irreducible fractions.
  • The number of fractions in the expression is limited to 10.

Space and Time Complexity

Time Complexity: O(n), where n is the number of characters in the expression. Space Complexity: O(1), as we only use a few integer variables for calculations.

Solution

To solve the problem, we will follow these steps:

  1. Parse the input string to extract individual fractions and their signs.
  2. Use the Least Common Multiple (LCM) to find a common denominator for all fractions.
  3. Convert each fraction to this common denominator and sum their numerators, taking care to apply the correct signs.
  4. Simplify the resulting fraction using the Greatest Common Divisor (GCD).
  5. Format the result appropriately as either an irreducible fraction or an integer in the form of a fraction.

We will use integer arithmetic throughout to avoid precision issues with floating-point numbers.

Code Solutions

from math import gcd

def fractionAddition(expression: str) -> str:
    # Initialize numerator and denominator for the result
    numerator, denominator = 0, 1
    # Split the expression into fractions
    fractions = []
    i = 0
    while i < len(expression):
        if expression[i] in "+-":
            sign = 1 if expression[i] == '+' else -1
            i += 1
        else:
            sign = 1
        
        # Extract numerator and denominator
        j = i
        while expression[j] != '/':
            j += 1
        num = sign * int(expression[i:j])
        i = j + 1
        j = i
        while j < len(expression) and expression[j] not in "+-":
            j += 1
        denom = int(expression[i:j])
        fractions.append((num, denom))
        i = j
    
    # Calculate the result
    for num, denom in fractions:
        # LCM of current denominator and new denominator
        lcm = denominator * denom // gcd(denominator, denom)
        # Update the numerator
        numerator = numerator * (lcm // denominator) + num * (lcm // denom)
        denominator = lcm
    
    # Reduce the fraction
    if numerator == 0:
        return "0/1"
    
    common_gcd = gcd(abs(numerator), denominator)
    numerator //= common_gcd
    denominator //= common_gcd
    
    return f"{numerator}/{denominator}"
← Back to All Questions