Fraction Addition and Subtraction - Video Solutions
Fraction Addition and Subtraction | Simple Simulation | Leetcode 592 | codestorywithMIK
Fraction Addition and Subtraction - Video Solution
Watch 10 video solutions for Fraction Addition and Subtraction, a medium level problem involving Math, String, Simulation. This walkthrough by codestorywithMIK has 13,079 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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:
- 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 is1, 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.
Approach Overview
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.
Complexity Analysis
| 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 |