Problem of The Day: Fraction Addition and Subtraction

Problem Statement

Intuition

When I first approached this problem, I immediately thought about the challenge of adding multiple fractions. My initial thought was that I needed to find a common denominator, sum up the numerators, and then simplify the result. This seemed like the most straightforward way to tackle the problem, so I decided to break down the expression into individual fractions and process each one.

Approach

To solve this problem, I took the following steps:

1. Split the Expression: I split the input expression into individual fractions. I used the replace method to handle both positive and negative fractions by converting any ‘-‘ signs into ‘+-‘ to preserve the correct signs.
2. Common Denominator Calculation: I calculated the common denominator by multiplying the denominators of all the fractions.
3. Summing Numerators: I adjusted the numerators according to the common denominator and summed them up.
4. Simplification: Finally, I simplified the resulting fraction by dividing both the numerator and denominator by their greatest common divisor (GCD).

Complexity

• Time complexity: The time complexity is mainly driven by the operations to compute the least common denominator and sum the numerators. In the worst-case scenario, this could be approximately \(O(n \cdot m)\), where n is the number of fractions and m is the average length of the denominators.
• Space complexity: The space complexity would be \(O(n)\) because I need to store the numerators and denominators separately before processing them.

Code

class Solution:
    def fractionAddition(self, expression: str) -> str:
        # Replace '-' with '+-' to manage negative fractions and split the expression
        exprs = expression.replace('-', '+-').split('+')
        res = 0
        numerators = []
        denominators = []

        # Extract numerators and denominators from each term
        for term in exprs:
            if term == '':
                continue
            n, d = term.split('/')
            numerators.append(int(n))
            denominators.append(int(d))

        # Calculate the common denominator
        denominator = 1
        for x in denominators:
            denominator *= x

        # Adjust numerators and sum them up
        numerator = 0
        for i in range(len(numerators)):
            numerator += (numerators[i] * denominator // denominators[i])

        # Simplify the fraction by dividing both numerator and denominator by their GCD
        for d in [2,3,5,7,9]:
            while (numerator % d == 0 and denominator % d == 0) and d != 1:
                numerator //= d
                denominator //= d

        # Return the final fraction as a string
        return str(numerator) + '/' + str(denominator)

Improved Code

class Solution:
    def fractionAddition(self, expression: str) -> str:
        # Replace '-' with '+-' to manage negative fractions and split the expression
        exprs = expression.replace('-', '+-').split('+')
        res = 0
        numerators = []
        denominators = []

        # Extract numerators and denominators from each term
        for term in exprs:
            if term == '':
                continue
            n, d = term.split('/')
            numerators.append(int(n))
            denominators.append(int(d))

        # Calculate the common denominator
        denominator = 1
        for x in denominators:
            denominator *= x

        # Adjust numerators and sum them up
        numerator = 0
        for i in range(len(numerators)):
            numerator += (numerators[i] * denominator // denominators[i])

        # Simplify the fraction by dividing both numerator and denominator by their GCD
        for d in [2,3,5,7,9]:
            while (numerator % d == 0 and denominator % d == 0) and d != 1:
                numerator //= d
                denominator //= d

        # Return the final fraction as a string
        return str(numerator) + '/' + str(denominator)

Editorial

Approach 1: Manual Parsing + Common Denominator

class Solution:
    def fractionAddition(self, expression):
        num = 0
        denom = 1

        i = 0
        while i < len(expression):
            curr_num = 0
            curr_denom = 0

            is_negative = False

            # check for sign
            if expression[i] == "-" or expression[i] == "+":
                if expression[i] == "-":
                    is_negative = True
                # move to next character
                i += 1

            # build numerator
            while i < len(expression) and expression[i].isdigit():
                val = int(expression[i])
                curr_num = curr_num * 10 + val
                i += 1

            if is_negative:
                curr_num *= -1

            # skip divisor
            i += 1

            # build denominator
            while i < len(expression) and expression[i].isdigit():
                val = int(expression[i])
                curr_denom = curr_denom * 10 + val
                i += 1

            # add fractions together using common denominator
            num = num * curr_denom + curr_num * denom
            denom = denom * curr_denom

        gcd = abs(self._find_gcd(num, denom))

        # reduce fractions
        num //= gcd
        denom //= gcd

        return f"{num}/{denom}"

    def _find_gcd(self, a, b):
        if a == 0:
            return b
        return self._find_gcd(b % a, a)

Approach 2 - Parsing with Regular Expressions

import re


class Solution:
    def fractionAddition(self, expression: str) -> str:
        num = 0
        denom = 1

        # separate expression into signed numbers
        nums = re.split("/|(?=[-+])", expression)
        nums = list(filter(None, nums))

        for i in range(0, len(nums), 2):
            curr_num = int(nums[i])
            curr_denom = int(nums[i + 1])

            num = num * curr_denom + curr_num * denom
            denom = denom * curr_denom

        gcd = abs(self._find_gcd(num, denom))

        num //= gcd
        denom //= gcd

        return str(num) + "/" + str(denom)

    def _find_gcd(self, a: int, b: int) -> int:
        if a == 0:
            return b
        return self._find_gcd(b % a, a)