Leetcode Daily Question 23/08/2024 - 592. Fraction Addition and Subtraction

Problem Description:

Given a string expression representing an expression of fraction addition and subtraction, return the calculation result in string format. The final result should be an irreducible fraction. If your final result is an integer, change it to the format of a fraction that has a denominator 1. So in this case, 2 should be converted to 2/1.

class Solution:
  def fracAddition(self, expression: str) -> str:
    numerator = 0
    denominator = 10 * 9 * 8 * 7 * 6
    if expression[0].isdigit():
        expression = "+" + expression
    n = len(expression)
    i = 0
    while i < n:
      sign = -1 if expression[i] == "-" else 1
      i += 1
      j = i
      while j < n and expression[j] not in "+-":
        j += 1
      
      top, bottom = expression[i:j].split("/")
      numberator += sign * int(top) * denominator // int(bottom)
      i = j 
    
    reduction_factor = gcd(numerator,denominator)
    numerator //= reduction_factor
    denominator //= reduction_factor
    return f"{numerator}/{denominator}"

Explanation:

The tricky part about this problem is the parsing of the string. The rest can be solve by following normal addition axioms.

It is also worth noting the constraints of the problem:

- 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.

This means we can set our initial denominator to include all possible combinations of 1 to 10 to make the process of making common the denominators between fractions easier.

So, we take the lowest common multiple of 1,2,3,4,5,6,7,8,9,10. Which is 10 * 9 * 8 * 7 * 6

numerator = 0
denominator = 10 * 9 * 8 * 7 * 6

Then, we check if the first fraction is negative. If not, we add an auxiliary "+" to the expression to make it regular.

if expression[0].isdigit():
  expression = "+" + expression

Now for the main calculation, we need to find where a fraction starts and ends and break it down into top part and bottom part.

To do this we use a nested while loop. We start by parsing the parity of the fraction. We then set another index tracker to start at the first number, and use a while loop to propagate the tracker until we reach the end of the current fraction.

Next is using the native split() method to split the fraction and perform the addition.

i = 0
n = 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
  top, bottom = expression[i:j].split()
  numerator += sign * int(top) * denominator // int(bottom)

Finally we reduce the fraction to its simplest form using the gcd() method in the math module.

We return the result as an f string.

reduction_factor = gcd(numerator, denominator)
numerator //= reduction_factor
denominator //= reduction_factor

return f"{numerator}/{denominator}"

The time complexity of this is O(n) as we only need to pass the string once.

The space complexity of this is O(1) as we only store independent variables.

The full solution can be found near the top of the page.