We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Fraction Addition and Subtraction

Number: 592

Difficulty: Medium

Paid? No

Companies: Zopsmart, IXL, Amazon

Problem Description

Given a string expression representing a series of fraction additions and subtractions (e.g., "-1/2+1/2" or "1/3-1/2"), calculate the result and return it as an irreducible fraction in the format "numerator/denominator". Even if the result is an integer, it must be represented as a fraction (for example, "2" should be returned as "2/1").

Key Insights

  • The problem involves parsing fractions from a string and handling both addition and subtraction operations.
  • A common denominator must be computed for performing arithmetic on fractions.
  • After calculating the resultant numerator and denominator, reduce the fraction using the greatest common divisor (GCD) to ensure it is irreducible.
  • Edge cases include negative results and ensuring proper sign handling.

Space and Time Complexity

Time Complexity: O(n * log(max(|numerators|, |denominators|))) where n is the number of fractions; since n is bounded by 10, it is effectively constant. Space Complexity: O(1)

Solution

The approach consists of the following steps:

  1. Parse the input string to extract individual fractions with their signs.
  2. Initialize a cumulative numerator and a denominator (starting with 0/1).
  3. For each extracted fraction, calculate a common denominator with the cumulative fraction, adjust the numerators accordingly, and combine them.
  4. After processing all fractions, compute the greatest common divisor (GCD) of the resulting numerator and denominator.
  5. Divide both the numerator and denominator by the GCD to simplify the fraction.
  6. Return the simplified fraction as a string formatted as "numerator/denominator".

We use basic arithmetic operations and the Euclidean algorithm for computing the GCD. Data structures needed are primarily integers for the numerator and denominator.

Code Solutions

# Python solution for Fraction Addition and Subtraction

from math import gcd

def fractionAddition(expression):
    # Initialize cumulative numerator and denominator (starting with 0/1)
    numerator, denominator = 0, 1
    i, n = 0, len(expression)
    
    # Iterate over the expression
    while i < n:
        # Read sign if present
        sign = 1
        if expression[i] in '+-':
            if expression[i] == '-':
                sign = -1
            i += 1
        
        # Parse the numerator of the current fraction
        value = 0
        while i < n and expression[i].isdigit():
            value = value * 10 + int(expression[i])
            i += 1
        currentNumerator = sign * value
        
        # Skip the '/' character
        i += 1
        
        # Parse the denominator of the current fraction
        value = 0
        while i < n and expression[i].isdigit():
            value = value * 10 + int(expression[i])
            i += 1
        currentDenominator = value
        
        # Update cumulative fraction: a/b + c/d = (a*d + b*c) / (b*d)
        numerator = numerator * currentDenominator + currentNumerator * denominator
        denominator *= currentDenominator
        
        # Simplify the fraction at each step to avoid overflow
        common_divisor = gcd(abs(numerator), denominator)
        numerator //= common_divisor
        denominator //= common_divisor

    # Return the result as a formatted string
    return str(numerator) + "/" + str(denominator)

# Example usage:
# print(fractionAddition("-1/2+1/2+1/3"))
← Back to All Questions