LeetCode 592: Fraction Addition and Subtraction Solution in Python – A Step-by-Step Guide

What Is LeetCode 592: Fraction Addition and Subtraction?

In LeetCode 592: Fraction Addition and Subtraction, you’re given a string expression containing fractions separated by + or - operators (e.g., "1/2 + 3/4"), and your task is to return the result as a simplified fraction in the form "numerator/denominator". Each fraction has an integer numerator and denominator, and the result must be reduced to its simplest form using the greatest common divisor (GCD). For example, with expression = "1/2 + 3/4 - 1/3", the result is "11/12". This problem builds on LeetCode 166: Fraction to Recurring Decimal for fraction handling but focuses on parsing and arithmetic with addition/subtraction.

Problem Statement

• Input: expression (str)—string of fractions with + or - operators.
• Output: String—simplified fraction result as "numerator/denominator".
• Rules: Fractions are integers; reduce using GCD; handle positive/negative signs.

Constraints

• 1 <= expression.length <= 10⁴
• Numerators and denominators are integers between -2³¹ and 2³¹ - 1
• Denominators are positive (1 to 2³¹ - 1)
• At least one fraction, valid expression

Examples

• Input: expression = "1/2 + 3/4"
• Output: "5/4"
• 1/2 + 3/4 = 2/4 + 3/4 = 5/4.
• Input: expression = "1/2 + 3/4 - 1/3"
• Output: "11/12"
• 1/2 + 3/4 - 1/3 = 6/12 + 9/12 - 4/12 = 11/12.
• Input: expression = "-1/2 + 1/2"
• Output: "0/1"
• -1/2 + 1/2 = 0/2 = 0/1.

Understanding the Problem: Adding Fractions

To solve LeetCode 592: Fraction Addition and Subtraction in Python, we need to parse a string into individual fractions, perform addition and subtraction by finding a common denominator, and simplify the result using GCD, handling up to 10⁴ characters efficiently. A brute-force approach computing the LCM (least common multiple) of all denominators could work but is overkill and slow (O(n * d), where d is product of denominators). Instead, a parsing and GCD-based method computes the sum incrementally in O(n) time, leveraging pairwise addition and reduction. We’ll explore:

• Best Solution (Parsing and GCD-Based Reduction): O(n) time, O(1) space—fast and optimal (n = string length).
• Alternative Solution (Brute-Force LCM Approach): O(n * d) time, O(1) space—thorough but inefficient.

Let’s dive into the GCD solution with a friendly breakdown!

Best Solution: Parsing and GCD-Based Reduction

Why GCD Wins

The parsing and GCD-based reduction solution is the best for LeetCode 592 because it computes the fraction sum in O(n) time and O(1) space by parsing the string into fractions, adding/subtracting them pairwise using a common denominator derived from GCD, and simplifying at each step, avoiding the need for a global LCM. It’s like mixing ingredients one-by-one, adjusting the recipe as you go, and serving a perfectly reduced dish—all in a swift, efficient process!

How It Works

Think of this as a fraction-mixing chef:

• Step 1: Parse Fractions:
• Split string by +, handle - signs, extract numerator/denominator.
• Step 2: GCD Helper:
• Compute GCD of two numbers to simplify fractions.
• Step 3: Add Fractions:
• For each fraction:
• Find common denominator with current result.
• Add/subtract numerators, update result.
• Simplify using GCD.
• Step 4: Format Result:
• Return "numerator/denominator" with proper sign.
• Why It Works:
• Incremental addition avoids large intermediates.
• GCD ensures simplest form at each step.

It’s like a fraction-adding maestro!

Step-by-Step Example

Example: expression = "1/2 + 3/4"

• Step 1: Parse:
• Fractions: ["1/2", "+3/4"].
• Step 2: Initialize result = (0, 1).
• Step 3: Add fractions:
• "1/2": num1 = 1, den1 = 2.
• Result (0/1) + 1/2:
• Common den = 2 * 1 // GCD(2, 1) = 2.
• New num = 0 2 + 1 1 = 1.
• Result = (1, 2).
• "+3/4": num2 = 3, den2 = 4.
• Result (1/2) + 3/4:
• Common den = 2 * 4 // GCD(2, 4) = 8.
• New num = 1 4 + 3 2 = 4 + 6 = 10.
• Result = (10, 8).
• GCD(10, 8) = 2, reduce to (5, 4).
• Step 4: Return "5/4".
• Result: "5/4".

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

• Step 1: Parse: ["-1/2", "+1/2"].
• Step 2: Result = (0, 1).
• Step 3:
• "-1/2": Result (0/1) + (-1/2) = (-1, 2).
• "+1/2": (-1/2) + 1/2 = (-1 + 1, 2) = (0, 2).
• GCD(0, 2) = 2, reduce to (0, 1).
• Step 4: Return "0/1".
• Result: "0/1".

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

Copy codeclass Solution:
    def fractionAddition(self, expression: str) -> str:
        def gcd(a: int, b: int) -> int:
            while b:
                a, b = b, a % b
            return abs(a)

        # Step 1: Parse fractions
        i, n = 0, len(expression)
        num, den = 0, 1  # Result fraction

        while i < n:
            # Handle sign
            sign = 1
            if expression[i] in '+-':
                if expression[i] == '-':
                    sign = -1
                i += 1

            # Parse numerator
            curr_num = 0
            while i < n and expression[i].isdigit():
                curr_num = curr_num * 10 + int(expression[i])
                i += 1
            curr_num *= sign

            # Skip '/'
            i += 1

            # Parse denominator
            curr_den = 0
            while i < n and expression[i].isdigit():
                curr_den = curr_den * 10 + int(expression[i])
                i += 1

            # Step 2: Add current fraction to result
            common_den = den * curr_den // gcd(den, curr_den)
            num = num * (common_den // den) + curr_num * (common_den // curr_den)
            den = common_den

            # Step 3: Simplify
            g = gcd(abs(num), den)
            num //= g
            den //= g

        # Step 4: Return formatted result
        return f"{num}/{den}"

• Lines 3-6: GCD helper using Euclidean algorithm.
• Lines 9-11: Initialize result fraction (0/1), pointer.
• Lines 13-35: Parse loop:
• Handle sign, extract numerator and denominator.
• Lines 38-41: Add fraction:
• Compute common denominator, update numerator, simplify with GCD.
• Line 44: Return "num/den".
• Time Complexity: O(n)—linear string parsing.
• Space Complexity: O(1)—constant extra space.

It’s like a fraction-summing wizard!

Alternative Solution: Brute-Force LCM Approach

Why an Alternative Approach?

The brute-force LCM approach computes the least common multiple of all denominators upfront, converts all fractions to this base, sums them, then simplifies, running in O(n * d) time (d = product of denominators) and O(n) space for parsed fractions. It’s thorough but inefficient due to large intermediates, making it a baseline for small inputs or understanding.

How It Works

Picture this as a fraction-blending brute:

• Step 1: Parse fractions into list.
• Step 2: Compute LCM of all denominators.
• Step 3: Convert and sum numerators.
• Step 4: Simplify with GCD, return result.

It’s like a heavy-duty fraction mixer!

Step-by-Step Example

Example: expression = "1/2 + 3/4"

• Step 1: Parse: [(1, 2), (3, 4)].
• Step 2: LCM(2, 4) = 4.
• Step 3: Convert:
• 1/2 = 2/4.
• 3/4 = 3/4.
• Sum = (2 + 3)/4 = 5/4.
• Step 4: GCD(5, 4) = 1, result = "5/4".
• Result: "5/4".

Code for Brute-Force Approach

Copy codeclass Solution:
    def fractionAddition(self, expression: str) -> str:
        def gcd(a: int, b: int) -> int:
            while b:
                a, b = b, a % b
            return abs(a)

        def lcm(a: int, b: int) -> int:
            return a * b // gcd(a, b)

        # Parse fractions
        fractions = []
        i, n = 0, len(expression)
        while i < n:
            sign = 1
            if expression[i] in '+-':
                if expression[i] == '-':
                    sign = -1
                i += 1
            num = 0
            while i < n and expression[i].isdigit():
                num = num * 10 + int(expression[i])
                i += 1
            i += 1  # Skip '/'
            den = 0
            while i < n and expression[i].isdigit():
                den = den * 10 + int(expression[i])
                i += 1
            fractions.append((sign * num, den))

        # Compute LCM of all denominators
        common_den = 1
        for _, den in fractions:
            common_den = lcm(common_den, den)

        # Sum numerators
        total_num = 0
        for num, den in fractions:
            total_num += num * (common_den // den)

        # Simplify
        g = gcd(abs(total_num), common_den)
        return f"{total_num // g}/{common_den // g}"

• Lines 3-12: GCD and LCM helpers.
• Lines 15-29: Parse fractions into list.
• Lines 32-34: Compute LCM of denominators.
• Lines 37-39: Convert and sum numerators.
• Lines 42-43: Simplify and return.
• Time Complexity: O(n * d)—LCM computation.
• Space Complexity: O(n)—fraction list.

It’s a brute-force fraction blender!

Comparing the Two Solutions

• GCD (Best):
• Pros: O(n), O(1), fast and elegant.
• Cons: Incremental parsing logic.
• LCM (Alternative):
• Pros: O(n * d), O(n), thorough.
• Cons: Inefficient for large denominators.

GCD wins for efficiency!

Additional Examples and Edge Cases

• Single fraction: Itself simplified.
• All zeros: "0/1".
• Negative result: Handled with sign.

GCD handles them all!

Complexity Recap

• GCD: Time O(n), Space O(1).
• LCM: Time O(n * d), Space O(n).

GCD’s the speed champ!

Key Takeaways

• GCD: Fraction finesse—learn at Python Basics!
• LCM: Heavy lifting.
• Fractions: Math is fun.
• Python: GCD or LCM, your pick!

Final Thoughts: Crunch Those Fractions!

LeetCode 592: Fraction Addition and Subtraction in Python is a mathy challenge. Parsing and GCD-based reduction is your fast track, while brute-force LCM offers a thorough dive. Want more? Try LeetCode 166: Fraction to Recurring Decimal or LeetCode 50: Pow(x, n). Ready to add? Head to Solve LeetCode 592 on LeetCode and simplify those fractions today!