592. Fraction Addition and Subtraction Solution

The problem

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 is 1, 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.

Approach 1: Using LCM for Common Denominator

This approach involves using the Least Common Multiple (LCM) to find a common denominator for all fractions. Then, add or subtract the numerators accordingly, and finally, simplify the resulting fraction.

Python

from math import gcd

def fractionAddition(expression: str) -> str:
    def lcm(a, b):
        return a * b // gcd(a, b)

    num, denom = 0, 1
    i, n = 0, len(expression)
    
    while i < n:
        sign = 1
        if expression[i] in '+-':
            sign = -1 if expression[i] == '-' else 1
            i += 1
        j = i
        while expression[j] != '/':
            j += 1
        num1 = int(expression[i:j]) * sign
        i = j + 1
        j = i
        while j < n and expression[j].isdigit():
            j += 1
        denom1 = int(expression[i:j])
        i = j

        common_denom = lcm(denom, denom1)
        num = num * (common_denom // denom) + num1 * (common_denom // denom1)
        denom = common_denom

    gcd_ = gcd(abs(num), denom)
    return f"{num // gcd_}/{denom // gcd_}"

Java

import java.util.*;

class Solution {
    public String fractionAddition(String expression) {
        int numerator = 0, denominator = 1, n, d;
        int sign = 1, i = 0;
        
        while (i < expression.length()) {
            sign = (expression.charAt(i) == '-') ? -1 : 1;
            if (expression.charAt(i) == '-' || expression.charAt(i) == '+') i++;
            
            int j = i;
            while (expression.charAt(j) != '/') j++;
            n = Integer.parseInt(expression.substring(i, j)) * sign;
            i = ++j;
            while (j < expression.length() && Character.isDigit(expression.charAt(j))) j++;
            d = Integer.parseInt(expression.substring(i, j));
            i = j;

            int lcmDen = denominator * (d / gcd(denominator, d));
            numerator = numerator * (lcmDen / denominator) + n * (lcmDen / d);
            denominator = lcmDen;
        }

        int gcd = gcd(Math.abs(numerator), denominator);
        numerator /= gcd;
        denominator /= gcd;

        return numerator + "/" + denominator;
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

C++

#include <iostream>
#include <sstream>
#include <numeric>
using namespace std;

string fractionAddition(string expression) {
    istringstream is(expression);
    int num = 0, den = 1, n, d;
    char slash, op = '+';
    while (is >> n >> slash >> d) {
        int common_den = den / gcd(den, d) * d;
        num = num * (common_den / den) + (op == '+' ? 1 : -1) * n * (common_den / d);
        den = common_den;
        op = is.peek();
        if (op == '+' || op == '-')
            is.get();
    }
    int gcd_ = abs(gcd(num, den));
    return to_string(num / gcd_) + '/' + to_string(den / gcd_);
}

JavaScript

function gcd(a, b) {
    return b === 0 ? a : gcd(b, a % b);
}

function fractionAddition(expression) {
    const lcm = (a, b) => a * b / gcd(a, b);

    let num = 0, den = 1, i = 0, n = expression.length;
    while (i < n) {
        let sign = 1;
        if (expression[i] === '-' || expression[i] === '+') {
            sign = expression[i] === '-' ? -1 : 1;
            i++;
        }

        let numStart = i;
        while (expression[i] !== '/') i++;
        let numerator = parseInt(expression.slice(numStart, i)) * sign;
        i++;
        let denomStart = i;
        while (i < n && !isNaN(parseInt(expression[i]))) i++;
        let denominator = parseInt(expression.slice(denomStart, i));

        const lcmDenom = lcm(den, denominator);
        num = num * (lcmDenom / den) + numerator * (lcmDenom / denominator);
        den = lcmDenom;
    }

    const commonDiv = gcd(Math.abs(num), den);
    return `${num / commonDiv}/${den / commonDiv}`;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int gcd(int a, int b) {
    while (b != 0) {
        int t = b;
        b = a % b;
        a = t;
    }
    return a;
}

int lcm(int a, int b) {
    return (a / gcd(a, b)) * b;
}

char* fractionAddition(char* expression) {
    int numerator = 0, denominator = 1, n, d;
    char sign, *ptr = expression;
    while (*ptr) {
        n = (*ptr == '-' || *ptr == '+') ? atoi(ptr) : 1;
        sign = (*ptr == '-') ? '-' : '+';
        ptr += (n == 1 ? 0 : (sign == '-' ? 1 : 2));
        d = atoi(strchr(ptr, '/') + 1);
        ptr = strchr(ptr, '/') + 1;
        ptr += (*ptr == '-') ? 1 : 0;
        
        int commonDen = lcm(denominator, d);
        numerator = numerator * (commonDen / denominator) + n * (commonDen / d);
        denominator = commonDen;
    }

    int commonDiv = gcd(abs(numerator), denominator);
    numerator /= commonDiv;
    denominator /= commonDiv;

    char *result = (char *)malloc(32);
    sprintf(result, "%d/%d", numerator, denominator);
    return result;
}

using System;

public class Solution {
    public string FractionAddition(string expression) {
        int numerator = 0, denominator = 1, num, dem;
        int sign = 1;
        for (int i = 0; i < expression.Length; ) {
            if (expression[i] == '-' || expression[i] == '+') {
                sign = expression[i] == '-' ? -1 : 1;
                i++;
            }
            int start = i;
            while (expression[i] != '/') i++;
            num = int.Parse(expression.Substring(start, i - start)) * sign;
            i++;
            start = i;
            while (i < expression.Length && Char.IsDigit(expression[i])) i++;
            dem = int.Parse(expression.Substring(start, i - start));

            int lcmDen = denominator * (dem / GCD(denominator, dem));
            numerator = numerator * (lcmDen / denominator) + num * (lcmDen / dem);
            denominator = lcmDen;
        }

        int gcd = GCD(Math.Abs(numerator), denominator);
        numerator /= gcd;
        denominator /= gcd;
        return numerator + "/" + denominator;
    }

    private int GCD(int a, int b) {
        return b == 0 ? a : GCD(b, a % b);
    }
}

The Python function is simple and concise - it utilizes helper functions like gcd and lcm to compute and combine fractions. Parsing and computation lead to a final simplification and output in irreducible form.

Complexity

Time Complexity: O(n) as parsing occurs at each step.
Space Complexity: O(1), keeping space usage minimal.

Try this approach in the editor

Approach 2: Consecutive Fraction Handling

In this method, we handle each fraction consecutively, updating the numerator and denominator dynamically. This maintains an accumulated result for fractions encountered sequentially.

Python

from math import gcd

def fraction_addition_consec(expression: str) -> str:
    def lcm(a, b):
        return a * b // gcd(a, b)

    num, den, i, n = 0, 1, 0, len(expression)
    while i < n:
        sign = 1
        if expression[i] == '+' or expression[i] == '-':
            sign = -1 if expression[i] == '-' else 1
            i += 1

        num_start = i
        while expression[i] != '/':
            i += 1
        numerator = int(expression[num_start:i]) * sign
        i += 1

        denom_start = i
        while i < n and expression[i].isdigit():
            i += 1
        denominator = int(expression[denom_start:i])

        lcm_denom = lcm(den, denominator)
        num = num * (lcm_denom // den) + numerator * (lcm_denom // denominator)
        den = lcm_denom

    gcd_ = gcd(abs(num), den)
    return f'{num // gcd_}/{den // gcd_}'

Java

public class Solution {
    public String fractionAdditionConsec(String expression) {
        int num = 0, den = 1;

        char[] chars = expression.toCharArray();
        int i = 0, n = chars.length;
        while (i < n) {
            int sign = 1;
            if (chars[i] == '+' || chars[i] == '-') {
                sign = chars[i] == '-' ? -1 : 1;
                i++;
            }
            int numerator = 0;
            while (i < n && chars[i] != '/') {
                numerator = numerator * 10 + (chars[i] - '0');
                i++;
            }
            numerator *= sign;
            i++;
            int denominator = 0;
            while (i < n && Character.isDigit(chars[i])) {
                denominator = denominator * 10 + (chars[i] - '0');
                i++;
            }
            int lcm = den * (denominator / gcd(den, denominator));
            num = num * (lcm / den) + numerator * (lcm / denominator);
            den = lcm;
        }

        int gcd = gcd(Math.abs(num), den);
        return (num / gcd) + "/" + (den / gcd);
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

C++

#include <iostream>
#include <numeric>
#include <sstream>
using namespace std;

string fractionAddConsecutive(string expression) {
    stringstream ss(expression);
    int num = 0, den = 1;
    int n, d;
    char op;

    while (ss >> n >> op >> d) {
        int lcmDenom = den * (d / gcd(den, d));
        num = num * (lcmDenom / den) + n * (lcmDenom / d);
        den = lcmDenom;

        if (ss >> op);
    }

    int gcd_ = gcd(abs(num), den);
    num /= gcd_;
    den /= gcd_;
    return to_string(num) + " / " + to_string(den);
}

JavaScript

function gcd(a, b) {
    return b === 0 ? a : gcd(b, a % b);
}

function fractionAddConsecutive(expression) {
    let num = 0, den = 1, i = 0, n = expression.length;

    while (i < n) {
        let sign = (expression[i] === '-' || expression[i] === '+') ? (expression[i++] === '-' ? -1 : 1) : 1;

        let num_start = i;
        while (expression[i] !== '/') i++;
        let numerator = parseInt(expression.slice(num_start, i)) * sign;
        i++;

        let denom_start = i;
        while (i < n && !isNaN(parseInt(expression[i]))) i++;
        let denominator = parseInt(expression.slice(denom_start, i));

        const lcm_denom = den * Math.floor(denominator / gcd(den, denominator));
        num = num * (lcm_denom / den) + numerator * (lcm_denom / denominator);
        den = lcm_denom;
    }

    const gcd_num = gcd(Math.abs(num), den);
    return `${num / gcd_num}/${den / gcd_num}`;
}

#include <stdio.h>
#include <stdlib.h>

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

char* fractionAdditionConsec(char* expression) {
    int num = 0, den = 1;
    for (char* p = expression; *p != '\0';) {
        int sign = 1;
        if (*p == '-' || *p == '+') {
            sign = (*p == '-') ? -1 : 1;
            p++;
        }
        int n = 0;
        while (*p != '/') {
            n = n * 10 + (*p - '0');
            p++;
        }
        n *= sign;
        p++;
        int d = 0;
        while (*p >= '0' && *p <= '9') {
            d = d * 10 + (*p - '0');
            p++;
        }
        int common = lcm(den, d);
        num = num * (common / den) + n * (common / d);
        den = common;
    }
    int g = gcd(abs(num), den);
    num /= g;
    den /= g;

    char* res = (char*)malloc(32);
    sprintf(res, "%d/%d", num, den);
    return res;
}

using System;

public class Solution {
    public string FractionAdditionConsec(string expression) {
        int num = 0, den = 1, n, d;
        int i = 0, sign = 1;

        while (i < expression.Length) {
            if (expression[i] == '+' || expression[i] == '-') {
                sign = (expression[i] == '-') ? -1 : 1;
                i++;
            }

            int numBegin = i;
            while (expression[i] != '/') i++;
            n = int.Parse(expression.Substring(numBegin, i - numBegin));
            n *= sign;
            i++;

            int dBegin = i;
            while (i < expression.Length && Expression[i] >= '0' && expression[i] <= '9') i++;
            d = int.Parse(expression.Substring(dBegin, i - dBegin));

            int lcmDenom = den * (d / GCD(den, d));
            num = num * (lcmDenom / den) + n * (lcmDenom / d);
            den = lcmDenom;
        }

        int gcd = GCD(Math.Abs(num), den);
        return (num / gcd) + "/" + (den / gcd);
    }

    private int GCD(int a, int b) {
        return b == 0 ? a : GCD(b, a % b);
    }
}

The Python function consolidates fractions by iterating through expression and maintaining a cumulative numerator and denominator, dynamically calculating the result for progressively encountered fractions.

Complexity

Time Complexity: O(n). Reflects the input size.
Space Complexity: O(1) owing to the minimal extra space usage.

Try this approach in the editor

Approach 3: Default Approach

func fractionAddition(expression string) string {
	x, y := 0, 6*7*8*9*10
	if unicode.IsDigit(rune(expression[0])) {
		expression = "+" + expression
	}
	i, n := 0, len(expression)
	for i < n {
		sign := 1
		if expression[i] == '-' {
			sign = -1
		}
		i++
		j := i
		for j < n && expression[j] != '+' && expression[j] != '-' {
			j++
		}
		s := expression[i:j]
		t := strings.Split(s, "/")
		a, _ := strconv.Atoi(t[0])
		b, _ := strconv.Atoi(t[1])
		x += sign * a * y / b
		i = j
	}
	z := gcd(abs(x), y)
	x /= z
	y /= z
	return fmt.Sprintf("%d/%d", x, y)
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Using LCM for Common Denominator	Time Complexity: O(n) as parsing occurs at each step. Space Complexity: O(1), keeping space usage minimal.
Consecutive Fraction Handling	Time Complexity: O(n). Reflects the input size. Space Complexity: O(1) owing to the minimal extra space usage.
Default Approach	–

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

Frequently asked questions

Is Fraction Addition and Subtraction easy or hard?

This problem is rated Medium because it mixes string parsing with fraction arithmetic. The logic itself is straightforward, but careful handling of signs, denominators, and fraction reduction is required to avoid mistakes.

Fraction Addition and Subtraction Python/Java solution

Both Python and Java implementations follow the same idea: parse each fraction, combine it with the running result using cross multiplication, and reduce using the gcd function. The logic stays O(n) with constant extra space.

How to solve Fraction Addition and Subtraction in O(n)?

Parse the expression from left to right and keep a running fraction result_num/result_den. For each new fraction, update the result using cross multiplication, then simplify using gcd(result_num, result_den). Since each character is processed once, the algorithm runs in O(n) time.

What is the best approach for Fraction Addition and Subtraction?

The most practical approach is consecutive fraction handling. Maintain a running numerator and denominator, combine each new fraction using cross multiplication, and reduce the result with GCD. This method processes the expression in one pass with O(n) time and O(1) space.

Is Fraction Addition and Subtraction asked at Google/Amazon/Meta?

Fraction manipulation and expression parsing problems appear in interviews at companies like Amazon and Google. They typically test string parsing, mathematical reasoning, and careful handling of integer arithmetic.

What data structure is used in Fraction Addition and Subtraction?

No complex data structure is required. The solution mainly uses integer variables to track numerators and denominators while scanning the string. The core techniques come from math operations and string parsing.

What is the time complexity of Fraction Addition and Subtraction?

The standard solutions run in O(n) time where n is the length of the input string. Each fraction is parsed once and combined using constant-time arithmetic operations and a GCD calculation.

Fraction Addition and Subtraction solution and explanation

The problem

Approach overview

Approach 1: Using LCM for Common Denominator

Approach 2: Consecutive Fraction Handling

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Fraction Addition and Subtraction solution and explanation

The problem

Approach overview

Approach 1: Using LCM for Common Denominator

Approach 2: Consecutive Fraction Handling

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems