Watch 10 video solutions for Fraction Addition and Subtraction, a medium level problem involving Math, String, Simulation. This walkthrough by codestorywithMIK has 12,829 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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"
Constraints:
'0' to '9', '/', '+' and '-'. So does the output.±numerator/denominator. If the first input fraction or the output is positive, then '+' will be omitted.[1, 10]. If the denominator is 1, it means this fraction is actually an integer in a fraction format defined above.[1, 10].Problem Overview: You receive a string representing addition and subtraction of fractions such as "-1/2+1/2+1/3". Each fraction has a numerator and denominator, and the final answer must be returned as an irreducible fraction. The challenge is parsing the string, combining fractions correctly, and simplifying the result using math operations like GCD or LCM.
Approach 1: Using LCM for Common Denominator (O(n) time, O(1) space)
Parse each fraction from the string and maintain a running numerator and denominator for the result. When a new fraction appears, compute the LCM of the current denominator and the new fraction’s denominator so both fractions share a common base. Convert both numerators to that denominator, perform the addition or subtraction, and update the result fraction. After each operation, simplify the fraction by dividing numerator and denominator by their gcd. The algorithm scans the string once while performing constant-time arithmetic per fraction, giving O(n) time complexity and O(1) extra space. This approach directly models real fraction arithmetic and is easy to reason about.
Approach 2: Consecutive Fraction Handling (O(n) time, O(1) space)
Instead of computing LCM every time, maintain a running fraction result_num/result_den. As you iterate through the expression, parse the sign, numerator, and denominator of the next fraction. Combine it with the running result using the formula:
result_num = result_num * den + sign * num * result_den
result_den = result_den * den
After each update, reduce the fraction using gcd(result_num, result_den). This effectively simulates consecutive fraction operations, which fits naturally with a single pass over the input. Parsing the expression is the main work, so the overall complexity remains O(n) time with O(1) space. The logic relies heavily on integer arithmetic and careful simulation of fraction evaluation.
Recommended for interviews: Consecutive Fraction Handling is usually the preferred solution. It keeps the implementation compact and avoids explicit LCM calculations while still producing simplified results. Interviewers typically look for correct fraction arithmetic, careful parsing of signs and denominators, and consistent fraction reduction with GCD. The LCM-based method is still valuable because it mirrors how fractions are taught mathematically, demonstrating strong fundamentals before optimizing the implementation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Using LCM for Common Denominator | O(n) | O(1) | When you want clear mathematical steps that mirror manual fraction addition |
| Consecutive Fraction Handling | O(n) | O(1) | General interview solution with compact implementation and single-pass parsing |