592. Fraction Addition and Subtraction
Model: qwen3.5:9b
Topics: Math
FAANG asked: 0
Acceptance rate: 50.3%
Problem Breakdown
We are given a string representing an arithmetic expression involving fractions (e.g., "1/2+1/3"). Our goal is to compute the sum of these fractions and return the result as an irreducible fraction in string format ("num/den").
Key Inputs: A single string containing digits, /, +, -.
Key Outputs: An irreducible fraction string. If the numerator divides evenly by the denominator (result is integer), we must still output it with a denominator of 1 (e.g., "2/1" instead of just "2").
Constraints & Edge Cases to Consider:
- Parsing Complexity: The input can start with an optional negative sign, or have operators between fractions. We need to tokenize the string correctly into
(numerator, denominator)pairs while preserving their signs (e.g.,-1/2vs+1/3). - Arithmetic Logic: Standard fraction addition requires a common denominator. Since we are summing multiple terms, maintaining a running total as an irreducible or non-reduced fraction is necessary before the final step to avoid intermediate overflow issues in languages with fixed-size integers (though Python handles large ints automatically).
- Simplification: The result must be irreducible. This means dividing both numerator and denominator by their Greatest Common Divisor (GCD) at the end.
- Sign Handling: Negative results should have the sign on the numerator, not before the fraction bar or as a separate operator in the output string format.
Intuition
A brute-force approach might try to convert everything to decimals and sum them up. However, floating-point arithmetic introduces precision errors (e.g., 1/3 cannot be represented exactly). We must use integer arithmetic throughout.
The core mathematical insight is that adding two fractions and results in:
We can maintain a running numerator (res_num) and denominator (res_den). For every new fraction n/d parsed from the string, we update our accumulator using cross-multiplication.
Why is this better? It avoids storing all intermediate fractions in memory (though space isn’t tight here) and keeps logic linear with respect to the number of terms. The critical step that makes it robust is parsing the input correctly into signed integers before doing any math, then simplifying only at the very end using math.gcd.
Approach
- Parsing: We need to extract all fractions from the string. A regex pattern like
[-+]?\d+/\d+works well here because it captures optional leading signs and ensures we get valid fraction tokens (numerator/denominator). This handles cases where a negative sign is at the start or between operators naturally. - Accumulation: Initialize our result accumulator as
(0, 1). Iterate through each parsed fraction tuple(n, d). Updateres_numandres_den:- New Numerator =
res_num * d + n * res_den - New Denominator =
res_den * d
- New Numerator =
- Simplification: After processing all fractions, calculate the GCD of the final numerator and denominator. Divide both by this GCD to ensure irreducibility.
- Formatting: Return the string formatted as
"num/den". Python’s integer formatting handles negative signs correctly (e.g.,-5), so we don’t need extra logic for outputting+2/1.
Complexity Analysis
- Time Complexity: , where is the length of the input string. We iterate through the string once to parse tokens and perform arithmetic operations proportional to the number of digits (which fits within standard integer limits). The GCD calculation takes logarithmic time relative to the values involved.
- Space Complexity: auxiliary space if we process fractions on the fly, or where is the number of terms stored during parsing. Given constraints (), this is negligible.
Solution
import re
from math import gcd
def fractionAddition(expression: str) -> str:
# Regex to find all fractions including their signs (e.g., -1/2, +3/4)
pattern = r'[-+]?\d+/\d+'
tokens = re.findall(pattern, expression)
res_num = 0
res_den = 1
for token in tokens:
# Parse numerator and denominator from the matched string
parts = token.split('/')
n = int(parts[0])
d = int(parts[1])
# Add current fraction to result using common denominator logic
# Formula: (res_num/den) + (n/d) -> (res_num * d + n * res_den) / (den * d)
new_numerator = res_num * d + n * res_den
new_denominator = res_den * d
res_num, res_den = new_numerator, new_denominator
# Simplify the fraction by dividing both parts by their GCD
common_divisor = gcd(res_num, res_den)
return f"{res_num // common_divisor}/{res_den // common_divisor}"
# Example usage:
print(fractionAddition("-1/2+1/2")) # Output: "0/1"
print(fractionAddition("5/3+1/3")) # Output: "2/1"
Edge Cases Handled
- Negative Result: The regex captures the negative sign in
n, so if the sum is negative,res_numwill be negative. Python’s string formatting preserves this (e.g.,-5/6). - Integer Output: If the result simplifies to an integer (denominator becomes 1 after GCD reduction), we output it as
"X/1", satisfying the requirement that integers must have a denominator of1. - Zero Result: If numerator is
0and denominator reduces, we get"0/1"which matches Example 1. - Parsing Ambiguity: The regex handles cases where the string starts with
-(e.g.,"-1/2") or has a leading+. It also correctly splits tokens even if multiple operators exist in sequence without spaces, as long as they are attached to numbers per problem constraints.