Problem Description

You are given a string expression that represents a mathematical expression containing fractions being added and subtracted. Your task is to evaluate this expression and return the result as a string.

The expression consists of fractions in the format a/b connected by + or - operators. For example: "-1/2+1/2" or "1/3-1/2".

The result must be returned as an irreducible fraction (simplified to its lowest terms). If the final result is a whole number, it should still be represented as a fraction with denominator 1. For instance, if the result is 2, it should be returned as "2/1".

Key requirements:

• Parse and evaluate the fraction arithmetic expression
• Return the result in its simplest form (reduced fraction)
• Whole numbers should be formatted as fractions with denominator 1
• The input expression will always be valid with proper fraction format

Examples:

• Input: "-1/2+1/2" → Output: "0/1" (since -1/2 + 1/2 = 0)
• Input: "1/3-1/2" → Output: "-1/6" (since 1/3 - 1/2 = 2/6 - 3/6 = -1/6)
• Input: "-1/2+1/2+1/3" → Output: "1/3" (since the sum equals 1/3)

Intuition

When adding or subtracting fractions, we need a common denominator. The key insight is that instead of finding the least common denominator for each pair of fractions as we go, we can use a universal common denominator that works for all possible fractions in the expression.

Since the problem constraints typically limit the denominators to small values (1 through 10), we can use the product 6 * 7 * 8 * 9 * 10 = 30240 as our universal denominator. This number is divisible by all possible denominators from 1 to 10, making it a suitable common denominator for any fraction we encounter.

The approach works as follows:

1. Start with a numerator of 0 and our universal denominator 30240
2. For each fraction a/b in the expression, convert it to have the common denominator: (a * 30240/b) / 30240
3. Add or subtract the converted numerators based on the operator
4. After processing all fractions, we have a single fraction with numerator x and denominator 30240
5. Simplify the final fraction by dividing both numerator and denominator by their GCD

The parsing strategy handles the signs carefully - if a fraction is preceded by a - sign, we treat it as negative. To simplify parsing, if the expression starts with a number (no sign), we prepend a + sign to maintain consistency.

This method avoids the complexity of repeatedly finding LCMs and adjusting denominators for each operation, making the implementation cleaner and more efficient.

Learn more about Math patterns.

Solution Approach

The implementation follows these steps:

1. Initialize the result fraction: Start with numerator x = 0 and denominator y = 30240 (which is 6 * 7 * 8 * 9 * 10). This denominator is divisible by all numbers from 1 to 10.

2. Normalize the expression: If the expression starts with a digit (positive fraction), prepend a + sign to make parsing uniform:

   if expression[0].isdigit():
       expression = '+' + expression

3. Parse and process each fraction: Use two pointers to iterate through the expression:

   • i tracks the current position
   • j finds the end of the current fraction

   For each fraction:

   • Determine the sign (+ gives 1, - gives -1)
   • Move i past the sign
   • Find j by scanning until the next + or - operator or end of string
   • Extract the fraction substring between i and j

4. Extract and convert each fraction:

   s = expression[i:j]
   a, b = s.split('/')

   • Split the fraction string by / to get numerator a and denominator b
   • Convert the fraction to have common denominator y: the equivalent numerator is sign * int(a) * y // int(b)
   • Add this to the running total: x += sign * int(a) * y // int(b)

5. Simplify the final result:

   z = gcd(x, y)
   x //= z
   y //= z

   • Find the GCD of the final numerator and denominator
   • Divide both by the GCD to get the irreducible fraction

6. Format and return: Return the result as a string in the format "numerator/denominator":

   return f'{x}/{y}'

The algorithm efficiently handles all fractions by using a universal common denominator, avoiding the need to compute LCMs for each pair of fractions. The time complexity is O(n) where n is the length of the expression string, and the space complexity is O(1) excluding the input string.

Example Walkthrough

Let's walk through the expression "1/3-1/2" step by step to illustrate the solution approach.

Step 1: Initialize

• Start with numerator x = 0 and universal denominator y = 30240
• This represents the fraction 0/30240

Step 2: Normalize expression

• The expression starts with '1' (a digit), so prepend '+'
• Expression becomes: "+1/3-1/2"

Step 3: Process first fraction "1/3"

• i = 0, pointing at '+'
• Sign is + (gives us sign = 1)
• Move i to 1 (past the sign)
• Find j by scanning forward: stop at position 4 (the - sign)
• Extract fraction: s = "1/3"
• Split: a = "1", b = "3"

Step 4: Convert and add first fraction

• Convert 1/3 to common denominator:
  • New numerator = sign * 1 * 30240 / 3 = 1 * 1 * 10080 = 10080
• Update running total: x = 0 + 10080 = 10080
• Current result: 10080/30240

Step 5: Process second fraction "1/2"

• Move i to 4 (the - sign)
• Sign is - (gives us sign = -1)
• Move i to 5 (past the sign)
• Find j: scan to end of string (position 8)
• Extract fraction: s = "1/2"
• Split: a = "1", b = "2"

Step 6: Convert and add second fraction

• Convert 1/2 to common denominator:
  • New numerator = sign * 1 * 30240 / 2 = -1 * 1 * 15120 = -15120
• Update running total: x = 10080 + (-15120) = -5040
• Current result: -5040/30240

Step 7: Simplify the final fraction

• Find GCD of -5040 and 30240:
  • GCD(-5040, 30240) = 5040
• Divide both by GCD:
  • x = -5040 / 5040 = -1
  • y = 30240 / 5040 = 6
• Final simplified fraction: -1/6

Step 8: Return result

• Return "-1/6"

This matches our expected output since 1/3 - 1/2 = 2/6 - 3/6 = -1/6.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of the expression string.

The algorithm performs a single pass through the expression string using a while loop that iterates from index 0 to n. Within each iteration:

• Finding the next operator sign (+ or -) takes O(1) time
• The inner while loop to find the end of the current fraction moves the pointer j forward, but each character is visited only once across all iterations
• Splitting the fraction string by / takes O(k) where k is the length of the current fraction substring (bounded by a constant since denominators and numerators are limited to at most 2 digits)
• Integer operations (multiplication, division) take O(1) time
• The gcd operation at the end takes O(log(min(x, y))) time, which is O(log(y)) = O(1) since y is bounded by a constant (6 * 7 * 8 * 9 * 10)

Since each character in the expression is processed exactly once and all operations within the loop are constant time, the overall time complexity is O(n).

Space Complexity: O(1)

The algorithm uses only a fixed amount of extra space:

• Integer variables x, y, i, j, n, sign, and z
• String variables s, a, and b which store fractions (bounded by constant size)
• The output string construction also uses constant space

The space used does not grow with the input size, resulting in O(1) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow with Large Common Denominator

The code uses common_denominator = 6 * 7 * 8 * 9 * 10 = 30240, which is unnecessarily large. When processing multiple fractions, the intermediate calculations (sign * int(fraction_numerator) * common_denominator // int(fraction_denominator)) can cause integer overflow issues in languages with fixed integer sizes, or lead to inefficient computations.

Solution: Use a smaller, more efficient common denominator or calculate the LCM dynamically:

def fractionAddition(self, expression: str) -> str:
    numerator = 0
    denominator = 1  # Start with denominator 1
  
    if expression[0].isdigit():
        expression = '+' + expression
  
    index = 0
    while index < len(expression):
        sign = -1 if expression[index] == '-' else 1
        index += 1
      
        fraction_end = index
        while fraction_end < len(expression) and expression[fraction_end] not in '+-':
            fraction_end += 1
      
        fraction_string = expression[index:fraction_end]
        frac_num, frac_den = map(int, fraction_string.split('/'))
      
        # Calculate LCM of current denominator and new fraction's denominator
        lcm = denominator * frac_den // gcd(denominator, frac_den)
      
        # Scale both fractions to have the LCM as denominator
        numerator = numerator * (lcm // denominator) + sign * frac_num * (lcm // frac_den)
        denominator = lcm
      
        # Reduce after each operation to prevent overflow
        g = gcd(abs(numerator), denominator)
        numerator //= g
        denominator //= g
      
        index = fraction_end
  
    return f'{numerator}/{denominator}'

2. Handling Edge Cases with Leading Signs

The current approach adds a '+' sign only when the expression starts with a digit. This fails to handle cases where the expression might start with a negative fraction that has no explicit sign for the numerator (though the problem guarantees proper format, defensive programming is important).

Solution: Use regex or more robust parsing:

import re

def fractionAddition(self, expression: str) -> str:
    # Use regex to find all fractions with their signs
    pattern = r'[+-]?\d+/\d+'
    fractions = re.findall(pattern, expression)
  
    numerator = 0
    denominator = 1
  
    for fraction in fractions:
        # Parse each fraction
        if '/' in fraction:
            parts = fraction.split('/')
            frac_num = int(parts[0])
            frac_den = int(parts[1])
          
            # Add to running total
            numerator = numerator * frac_den + frac_num * denominator
            denominator = denominator * frac_den
          
            # Simplify to prevent overflow
            g = gcd(abs(numerator), denominator)
            numerator //= g
            denominator //= g
  
    return f'{numerator}/{denominator}'

3. Not Simplifying During Computation

The original code only simplifies at the end, which can lead to very large intermediate values even when the final result is small.

Solution: Simplify after each addition to keep numbers manageable:

# After adding each fraction, immediately simplify
numerator += sign * frac_num * (denominator // frac_den)
g = gcd(abs(numerator), denominator)
if g > 1:  # Only divide if there's a common factor
    numerator //= g
    denominator //= g

These improvements make the solution more robust, efficient, and less prone to numerical issues while maintaining the same O(n) time complexity.