Fraction Addition and Subtraction

medium math string

Problem

Given a string of signed fractions concatenated, return the result in reduced form 'num/den'.

Inputexpression = '-1/2+1/2+1/3'

Output'1/3'

Walk left to right, keep a running fraction.

input

def fraction_addition(expr):
    from math import gcd
    import re
    parts = re.findall(r'[+-]?\d+/\d+', expr if expr[0] in '+-' else '+' + expr)
    n, d = 0, 1
    for p in parts:
        a, b = map(int, p.split('/'))
        n, d = n * b + a * d, d * b
        g = gcd(abs(n), abs(d)); n //= g; d //= g
    return f'{n}/{d}'

function fractionAddition(expr) {
  const gcd = (a, b) => b ? gcd(b, a % b) : a;
  const parts = (expr[0] === '-' ? expr : '+' + expr).match(/[+-]\d+\/\d+/g);
  let n = 0, d = 1;
  for (const p of parts) {
    const [a, b] = p.split('/').map(Number);
    n = n * b + a * d; d = d * b;
    const g = gcd(Math.abs(n), Math.abs(d)); n /= g; d /= g;
  }
  return `${n}/${d}`;
}

String fractionAddition(String expr) {
    if (expr.charAt(0) != '-') expr = "+" + expr;
    long n = 0, d = 1; int i = 0;
    while (i < expr.length()) {
        int j = i + 1; while (j < expr.length() && "+-".indexOf(expr.charAt(j)) < 0) j++;
        String[] parts = expr.substring(i, j).split("/");
        long a = Long.parseLong(parts[0]), b = Long.parseLong(parts[1]);
        n = n * b + a * d; d = d * b;
        long g = gcd(Math.abs(n), Math.abs(d)); n /= g; d /= g;
        i = j;
    }
    return n + "/" + d;
}
long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); }

string fractionAddition(string expr) {
    if (expr[0] != '-') expr = "+" + expr;
    long long n = 0, d = 1; int i = 0;
    while (i < (int) expr.size()) {
        int j = i + 1; while (j < (int) expr.size() && expr[j] != '+' && expr[j] != '-') j++;
        size_t slash = expr.find('/', i);
        long long a = stoll(expr.substr(i, slash - i)), b = stoll(expr.substr(slash + 1, j - slash - 1));
        n = n * b + a * d; d = d * b;
        long long g = __gcd(abs(n), abs(d)); n /= g; d /= g;
        i = j;
    }
    return to_string(n) + "/" + to_string(d);
}

Explanation

The idea is to keep a single running fraction n/d and fold each fraction from the expression into it, one at a time, just like you would add fractions by hand.

First we split the string into individual signed fractions. A small trick handles the sign: if the expression does not start with a sign we prepend a +, so a pattern like [+-]\d+/\d+ can grab every term cleanly, including its sign.

To add a new fraction a/b to the running n/d, we use the cross-multiply rule: the new numerator is n*b + a*d and the new denominator is d*b. After each step we divide both by their greatest common divisor (gcd) so the numbers stay small and the final fraction is fully reduced.

Example: -1/2 + 1/2 + 1/3. Start at 0/1. Adding -1/2 gives -1/2. Adding 1/2 gives 0/4, which reduces to 0/1. Adding 1/3 gives 1/3.

Because we process each term once and the gcd step keeps values bounded, the whole thing runs in O(n) over the length of the string.

Time: O(n) Space: O(1)