#592

Medium

LeetCode Problem Workspace

Fraction Addition and Subtraction

Solve fraction addition and subtraction by handling expressions, calculating results, and simplifying fractions to irreducible form.

math string simulation

Problem Statement

Given a string representing an expression involving fraction addition and subtraction, calculate the result in irreducible fraction form. The expression will consist of fractions represented by the format ±numerator/denominator, with numbers between 1 and 10. The result should be presented as a fraction, and if it simplifies to an integer, format it as integer/1.

For example, in the expression '-1/2+1/2', the result is '0/1'. The solution must handle multiple fractions and ensure the denominator is non-zero. Input can include addition and subtraction operations between fractions, and the final result should be irreducible. If the result is an integer, output it in fraction form, such as '2/1'.

Examples

Example 1

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

Output: "0/1"

Example details omitted.

Example 2

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

Output: "1/3"

Example details omitted.

Example 3

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

Output: "-1/6"

Example details omitted.

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.

Solution Approach

Parse the Expression

First, split the input string into individual fractions. Carefully account for operators and negative signs while extracting each fraction. This step ensures that the correct fractions are isolated for further processing.

Find the Least Common Denominator (LCD)

For each operation (addition or subtraction), calculate the least common denominator between the two fractions. This step is key to ensuring that fractions are compatible for addition or subtraction.

Simplify the Result

Once the operation is complete, reduce the resulting fraction to its simplest form. This involves finding the greatest common divisor (GCD) of the numerator and denominator and dividing both by the GCD. If the denominator is 1, return the numerator as an integer.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(\log(\min(a, b)))

The time complexity is O(n) where n is the number of fractions in the expression, since we only iterate through the fractions and their operations once. The space complexity is O(log(min(a, b))) due to the GCD calculation when simplifying the fraction result, where a and b are the numerators or denominators of the fractions.

What Interviewers Usually Probe

The candidate demonstrates a clear understanding of fraction arithmetic and simplification.
They can efficiently manipulate strings to parse and handle fractions correctly.
The candidate can break down complex mathematical problems into simpler, manageable steps, ensuring correctness in the final result.

Common Pitfalls or Variants

Common pitfalls

Misinterpreting the sign of a fraction when parsing the string can lead to incorrect results.
Forgetting to simplify the resulting fraction to its irreducible form can cause unnecessary complexity in the answer.
Overcomplicating the process by not handling fractions step by step, which could lead to inefficient or erroneous calculations.

Follow-up variants

Handling more complex expressions with mixed operations (e.g., multiple additions and subtractions in the same expression).
Returning the result as a decimal instead of a fraction, while maintaining accuracy.
Working with fractions that involve larger numbers, requiring more efficient GCD algorithms.

FAQ

What is the best approach to solve Fraction Addition and Subtraction?

The best approach is to parse the string into fractions, compute the least common denominator, and simplify the result. This ensures accurate handling of both addition and subtraction operations.

How can I handle negative fractions in this problem?

You should account for negative signs when parsing the fraction strings and ensure that the final result properly reflects these signs in the output fraction.

Can the result be an integer?

Yes, if the result of the fraction operations simplifies to an integer, it should be returned in the format 'integer/1'.

What is the expected time complexity for solving Fraction Addition and Subtraction?

The time complexity is O(n), where n is the number of fractions in the expression. Each fraction and operation is processed once.

What are the key challenges when solving Fraction Addition and Subtraction?

The key challenges involve correctly parsing the string to identify fractions and signs, calculating the least common denominator, and reducing the result to its simplest form.

terminal

Solution

Solution 1

#### Python3

class Solution:
    def fractionAddition(self, expression: str) -> str:
        x, y = 0, 6 * 7 * 8 * 9 * 10
        if expression[0].isdigit():
            expression = '+' + expression
        i, n = 0, len(expression)
        while i < n:
            sign = -1 if expression[i] == '-' else 1
            i += 1
            j = i
            while j < n and expression[j] not in '+-':
                j += 1
            s = expression[i:j]
            a, b = s.split('/')
            x += sign * int(a) * y // int(b)
            i = j
        z = gcd(x, y)
        x //= z
        y //= z
        return f'{x}/{y}'

Continue Practicing

#640 solve the equation #537 complex number multiplication #415 add strings