Total of a Fraction Expression
MediumMath & Geometry
Problem
A recipe scaler writes ingredient adjustments as a chain of fractions joined by + and -, for example "-1/2+1/3+1/6". The first fraction may start with a minus sign; there are no spaces.
Evaluate the expression and return the result as an irreducible fraction "p/q" with q > 0. A whole number is written with denominator 1, and zero is "0/1".
Example 1
- Input:
- expression = "-1/2+1/3+1/6"
- Output:
- "0/1"
-3/6 + 2/6 + 1/6 = 0.
Example 2
- Input:
- expression = "1/3-1/2"
- Output:
- "-1/6"
Example 3
- Input:
- expression = "3/4"
- Output:
- "3/4"
Constraints
- 1 to 20 fractions
- Each numerator is between 0 and 100 and each denominator between 1 and 20
- The expression is well formed: an optional leading '-', then fractions separated by '+' or '-'
Hint
Show the first hint
Keep a running fraction num/den, starting at 0/1, and add one term at a time.
Walkthrough
How to approach it
01Clarify before coding
- Can the first term be negative? Yes, with a leading '-'. Later terms are always preceded by '+' or '-'.
- How is zero written? "0/1".
- Where does the sign go? On the numerator; the denominator is always positive.
- Can numbers grow too large? After reducing at each step the denominator divides lcm(1..20) = 232792560, so everything stays well inside safe integers.
02Brute force
Bring all terms to one common denominator, the product of all denominators, and add the numerators.
Cost: O(k) arithmetic, but the product of 20 denominators up to 20 reaches about 10^26, overflowing 64-bit integers.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.