algoadvance

You are given a string expression representing an expression of fractions. The fractions will be added and subtracted. The fraction values are provided as a string format “a/b” where a is the numerator and b is the non-zero denominator. The input string is an expression where the fractions are joined by ‘+’ or ‘-‘.

Your task is to return the result of this expression in its simplest form as a string in the format “numerator/denominator”.

Example 1:
Input: expression = "-1/2+1/2"
Output: "0/1"

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

Example 3:
Input: expression = "1/3-1/2"
Output: "-1/6"

Clarifying Questions

1. Q: Will the input always be a valid expression? A: Yes, the input string expression will always be a valid fraction expression as per the problem constraints.

2. Q: How should we handle zero denominators? A: Each fraction will have a non-zero denominator as per the problem constraints.

3. Q: What is the maximum length of the input expression? A: The problem does not specify, but we should assume it can be relatively large, but manageable within typical constraints for algorithmic problems on LeetCode.

Strategy

To solve this problem, we will:

1. Parse the given expression to separate each fraction component.
2. Convert all fractions to have a common denominator.
3. Perform the addition or subtraction of the numerators.
4. Simplify the resulting fraction by dividing both numerator and denominator by their greatest common divisor (GCD).

Steps:

1. Tokenize the input expression to get all numerators and denominators.
2. Use Python’s fractions.Fraction to handle the arithmetic of fractions and simplify them.

Code

from fractions import Fraction

def fractionAddition(expression: str) -> str:
    # Split the expression into components of fractions, while preserving +/- signs
    fractions = []
    i = 0
    n = len(expression)
    
    while i < n:
        # Read the sign (either + or -)
        if expression[i] in '+-':
            sign = 1 if expression[i] == '+' else -1
            i += 1
        else:
            sign = 1
        
        # Read the fraction
        start = i
        while i < n and expression[i] != '+' and expression[i] != '-':
            i += 1
        
        numerator, denominator = expression[start:i].split('/')
        numerator = sign * int(numerator)
        denominator = int(denominator)
        fractions.append(Fraction(numerator, denominator))
    
    # Sum all fractions
    result = sum(fractions, start=Fraction(0, 1))
    
    # Convert result to string in the form "numerator/denominator"
    return f"{result.numerator}/{result.denominator}"

# Test Cases
print(fractionAddition("-1/2+1/2"))          # Output: "0/1"
print(fractionAddition("-1/2+1/2+1/3"))      # Output: "1/3"
print(fractionAddition("1/3-1/2"))           # Output: "-1/6"

Time Complexity

• Parsing: O(n) where n is the length of the input string (since we are iterating through the string once).
• Summation of Fractions: Given that we are using the fractions.Fraction class, which is designed to handle arithmetic and simplification of fractions efficiently, its time complexity can be considered O(1) for each fractional operation. However, summing k fractions can involve dealing with larger numerators and denominators as intermediates.
• Overall: The primary complexity lies in parsing the input expression and the number of fractional operations. Thus, the overall time complexity is O(n), where n is the length of the input string.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?