1415. Add Two Fractions Without Overflowing

For each query add the fractions p1/q1 and p2/q2 and print the sum in lowest terms. The numerators may be negative; the denominators are positive.

1/2 + 1/3 -> 5/6 1/2 + 1/2 -> 1/1 1/2 + -1/2 -> 0/1

## The sign rule, pinned before anything is asserted

A fraction has more than one reduced spelling unless the sign is placed by a rule: -1/2 and 1/-2 are the same number. So this problem requires

• the denominator positive,
• the sign carried by the numerator,
• zero written exactly 0/1.

Without that sentence the five reference languages would disagree and the problem would be unanswerable rather than hard.

Problem 99 adds two fractions as an introduction to structures, with small values. Here the values reach 10^9, which is what makes the order of the operations matter.

## What most people try first

num = p1*q2 + p2*q1 over den = q1*q2, then reduce. The answer it produces is right, and with q1 and q2 both near 10^9 the denominator q1*q2 is near 10^18, which still fits a signed 64-bit integer. But then the numerator is p1*q2 + p2*q1 with every factor near 10^9, so each product is near 10^18 and the **sum is near 2 * 10^18**. That still fits, barely, and it is worth knowing that the margin is only a factor of four: push the inputs to 10^10 and it would not.

The version that genuinely fails is num = p1*q2 + p2*q1 computed in 32-bit arithmetic, where 10^18 is hopeless.

## Use the lcm, not the product

The smallest denominator that works is the least common multiple:

g = gcd(q1, q2) den = q1 / g * q2 the lcm, dividing BEFORE multiplying num = p1 * (q2 / g) + p2 * (q1 / g)

Written q1 * q2 / g instead, the numerator overflows before the division can shrink it; written as above, nothing larger than the lcm is ever formed. When the two denominators share a factor this is strictly smaller than the product, and the numerator shrinks by the same factor.

Then reduce the result by its own gcd, because the lcm is not always the final denominator: 1/6 + 1/10 has lcm 30 and numerator 5 + 3 = 8, and 8/30 still reduces to 4/15.

## Why it is correct

den is a common multiple of q1 and q2, so den/q1 = q2/g and den/q2 = q1/g are integers and the rewrite p1/q1 = p1*(q2/g) / den is exact. Adding then only adds numerators. The final reduction is the argument of problem 1414.

## Overflow

Each product is two values near 10^9, so near 10^18, and their sum reaches about 2 * 10^18. That fits a signed 64-bit integer, whose limit is 9223372036854775807, and a signed 32-bit integer stops at 2147483647, so a 32-bit build answers 1999999999/1808348672 where the truth is 1999999999/999999999000000000. In JavaScript 2 * 10^18 is past 2^53, so BigInt is required. Dividing before multiplying is what keeps the margin: it is not needed for these bounds but it is free, and it is the habit that survives a change of constraints.

## Cost

O(log q) per query.

Constraints - `1 ≤ q ≤ 1000` - `-1000000000 ≤ p1, p2 ≤ 1000000000` - `1 ≤ q1, q2 ≤ 1000000000`