LeetCode 592 - Fraction Addition and Subtraction

The problem requires computing the result of a mathematical expression containing fractions with addition and subtraction operators. The input is a single string, expression, which consists of positive or negative fractions in the format numerator/denominator.

leetcodemediummathstringsimulation

LeetCode Problem 592

Difficulty: 🟡 Medium
Topics: Math, String, Simulation

Solution

Problem Understanding

The problem requires computing the result of a mathematical expression containing fractions with addition and subtraction operators. The input is a single string, expression, which consists of positive or negative fractions in the format numerator/denominator. The output must be an irreducible fraction, represented as a string in the same format. If the result is an integer, it should be represented as integer/1.

The key constraints are that each fraction in the input is irreducible, with numerators and denominators between 1 and 10, and the total number of fractions is small, between 1 and 10. These constraints imply that the solution does not need to worry about extremely large numbers of fractions or extremely large numerators/denominators, but correct arithmetic and simplification are crucial.

Edge cases that could trip up a naive implementation include negative fractions, sequences of consecutive additions and subtractions, and results that reduce to zero or to an integer. For example, handling -1/2+1/2 must return 0/1, not 0 or an incorrect fraction. The input guarantees valid fractions, so parsing can assume the format is correct, but simplification must be performed at the end.

Approaches

A brute-force approach would be to parse each fraction, convert it to a floating-point number, sum them all, and then attempt to convert the sum back into a fraction. While this works for small inputs, floating-point arithmetic introduces precision errors, and converting back to an irreducible fraction can be tricky. This method is unreliable because the output must be exact and irreducible.

The optimal approach uses exact arithmetic by maintaining numerators and denominators separately. For each fraction, we compute a common denominator and perform addition or subtraction using integer arithmetic. After processing all fractions, we simplify the result using the greatest common divisor (GCD) to ensure the fraction is irreducible. This method guarantees precision and correctness for any input within the constraints.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Convert to floats and back; may produce precision errors
Optimal O(n) O(1) Use integer arithmetic with GCD to maintain exact fractions

Algorithm Walkthrough

  1. Initialize a numerator num and denominator den to represent the running sum, starting at 0/1.
  2. Parse the input string to extract fractions, taking care to handle positive and negative signs explicitly.
  3. For each fraction, extract its numerator and denominator.
  4. Compute the new numerator for the running sum using the formula num * frac_den + frac_num * den, where frac_num and frac_den are the numerator and denominator of the current fraction.
  5. Update the denominator to be den * frac_den to maintain a common denominator.
  6. Reduce the resulting numerator and denominator by their greatest common divisor (GCD) after processing all fractions.
  7. Return the result as a string in the format numerator/denominator.

Why it works: This algorithm maintains an invariant that the running sum is always represented as a single fraction. Each addition or subtraction is performed using exact integer arithmetic, so no precision is lost. Simplifying at the end guarantees the result is irreducible, satisfying the problem constraints.

Python Solution

from math import gcd

class Solution:
    def fractionAddition(self, expression: str) -> str:
        import re
        # Initialize running numerator and denominator
        num, den = 0, 1
        
        # Extract all fractions with their signs
        fractions = re.findall(r'[+-]?\d+/\d+', expression)
        
        for frac in fractions:
            n, d = map(int, frac.split('/'))
            # Compute the new numerator with common denominator
            num = num * d + n * den
            den *= d
            # Reduce fraction at each step to avoid overflow
            g = gcd(abs(num), den)
            num //= g
            den //= g
        
        return f"{num}/{den}"

The Python solution uses regex to reliably extract each fraction, including its sign. For each fraction, we update the running numerator and denominator using integer arithmetic. We apply GCD at each step to keep the numbers small and simplify the result. Finally, the fraction is formatted as a string.

Go Solution

package main

import (
    "fmt"
    "strconv"
    "strings"
)

func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a%b
    }
    return a
}

func fractionAddition(expression string) string {
    num, den := 0, 1
    i := 0
    for i < len(expression) {
        sign := 1
        if expression[i] == '+' || expression[i] == '-' {
            if expression[i] == '-' {
                sign = -1
            }
            i++
        }
        j := i
        for j < len(expression) && expression[j] != '+' && expression[j] != '-' {
            j++
        }
        frac := expression[i:j]
        parts := strings.Split(frac, "/")
        n, _ := strconv.Atoi(parts[0])
        d, _ := strconv.Atoi(parts[1])
        n *= sign
        num = num*d + n*den
        den *= d
        g := gcd(abs(num), den)
        num /= g
        den /= g
        i = j
    }
    return fmt.Sprintf("%d/%d", num, den)
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

In Go, parsing requires manually iterating through the string because Go does not have as concise regex as Python. The logic for updating the numerator, denominator, and applying GCD remains the same. We handle signs explicitly, and the fraction is formatted using fmt.Sprintf.

Worked Examples

Example 1: "-1/2+1/2"

Step num den Fraction processed
Init 0 1 -
"-1/2" -1 2 -1/2
"+1/2" 0 1 0/1

Result: "0/1"

Example 2: "-1/2+1/2+1/3"

Step num den Fraction processed
Init 0 1 -
"-1/2" -1 2 -1/2
"+1/2" 0 1 0/1
"+1/3" 1 3 1/3

Result: "1/3"

Example 3: "1/3-1/2"

Step num den Fraction processed
Init 0 1 -
"1/3" 1 3 1/3
"-1/2" -1 6 -1/6

Result: "-1/6"

Complexity Analysis

Measure Complexity Explanation
Time O(n) We iterate through each fraction exactly once, performing integer arithmetic and GCD operations.
Space O(n) Space for storing parsed fractions (in Python) or constant in Go if parsed on the fly.

The algorithm is efficient because each fraction is processed in constant time, and the number of fractions is small, bounded by 10. Simplification with GCD ensures the numbers remain manageable.

Test Cases

# Provided examples
assert Solution().fractionAddition("-1/2+1/2") == "0/1"  # sum to zero
assert Solution().fractionAddition("-1/2+1/2+1/3") == "1/3"  # positive result
assert Solution().fractionAddition("1/3-1/2") == "-1/6"  # negative result

# Boundary values
assert Solution().fractionAddition("1/1") == "1/1"  # single integer fraction
assert Solution().fractionAddition("-1/1") == "-1/1"  # negative integer fraction

# Multiple fractions with simplification
assert Solution().fractionAddition("1/2+1/4+1/4") == "1/1"  # sums to integer
assert Solution().fractionAddition("1/2-1/4+1/8") == "3/8"  # mixed operations
Test Why
"-1/2+1/2" sum to zero, handles negative and positive cancellation
"-1/2+1/2+1/3" sum includes non-zero positive fraction
"1/3-1/2" result is negative and requires simplification
"1/1" single fraction, integer format
"-1/1" single negative fraction
"1/2+1/4+1/4" sums to integer, checks simplification
"1/2-1/4+1/8" mixed signs and fractions requiring common denominator

Edge Cases

One important edge case is when the result is zero. A naive implementation may return 0 instead of 0/1. By maintaining numerator and denominator separately and simplifying at the