Leetcode 592. Fraction Addition and Subtraction

Problem:

Given a string that represents a fraction addition or subtraction expression, the task is to calculate the result and return it as a string. The fraction should be irreducible (in its simplest form) and written as a numeral / denominator. If the value is a whole number, it should still be returned in the format of a fraction with denominator 1.

Approach:

The problem can be solved using a simple mathematical formula for fraction addition and subtraction and the built-in GCD (Greatest Common Divisor) function.

The formula for adding two fractions (A/B and a/b) is (Ab + aB) / Bb. This formula is used in every iteration of the loop where we parse each fraction from the input string.

In each iteration inside while loop:

• Parse the fractions a and b from the input string.
• Update the fractions A and B using the formula (Ab + aB) / Bb.
• Next step is simplifying the fraction A/B. This is done by finding the GCD of A and B and dividing A and B by their GCD. This ensures that the fraction is in its simplest form.

Finally, convert the final simplified fraction to a string and return it.

Example: Let's say the input is "5/3+1/3", into the loop we will get 5 as a, 3 as b then A will be calculated as 0, B will be 3 and then we will get next fraction 1 as a and 3 as b and the formula will be applied accordingly. After all calculations the output will be "2/1"

In Python:

1
2
3from fractions import Fraction
4
5class Solution:
6    def fractionAddition(self, s: str) -> str:
7        # split the input string on '+' and '-'
8        input_lst = s.replace('+', ' +').replace('-', ' -').split()
9        # to hold the fractions
10        fractions = [Fraction(i) for i in input_lst]
11        # returns the total of fractions in reduced form
12        return str(sum(fractions))

In Java:

1
2
3import java.math.*;
4import java.util.*;
5
6public class Solution {
7    public String fractionAddition(String expression) {
8        Scanner sc = new Scanner(expression).useDelimiter("/|(?=[-+])");
9        int A = 0, B = 1;
10        while (sc.hasNext()) {
11            int a = sc.nextInt(), b = sc.nextInt();
12            A = A * b + a * B;
13            B = B * b;
14            int g = gcd(A, B);
15            A /= g;
16            B /= g;
17        }
18        return A + "/" + B;
19    }
20
21    private int gcd(int a, int b) {
22        return b > 0 ? gcd(b, a % b) : a;
23    }
24}

In javascript:

1
2
3class Solution {
4    fractionAddition(expression) {
5        let fractions = expression.split(/(?=[+-])/);
6        let numerators = [], denominators = [];
7        fractions.forEach(f => {
8            let nodes = f.split("/");
9            numerators.push(parseInt(nodes[0]));
10            denominators.push(parseInt(nodes[1]));
11        });
12        let lcm = denominators[0];
13        for (let i = 1; i < denominators.length; i++) {
14            lcm = (denominators[i] * lcm) / this.gcd(denominators[i], lcm);
15        }
16        let numerator = 0;
17        for (let i = 0; i < numerators.length; i++) {
18            numerator += numerators[i] * (lcm / denominators[i]);
19        }
20        let gcd = this.gcd(numerator, lcm);
21        return `${numerator/gcd}/${lcm/gcd}`;
22    }
23
24    gcd(a, b) {
25        return b == 0 ? Math.abs(a) : this.gcd(b, a % b);
26    }
27}

In C++:

1
2
3#include<string>
4#include<sstream>
5
6using namespace std;
7
8class Solution {
9public:
10    string fractionAddition(string expression) {
11        istringstream iss(expression);
12        char _;
13        int a, b;
14        int A = 0, B = 1;
15
16        while (iss >> a >> _ >> b) {
17            A = A * b + a * B;
18            B *= b;
19            const int g = __gcd(A, B);
20            A /= g;
21            B /= g;
22        }
23
24        return to_string(A) + "/" + to_string(B);
25    }
26};

In C#:

1
2
3public class Solution {
4    public string FractionAddition(string expression) {
5        int A = 0, B = 1;
6        int i = 0;
7        while (i < expression.Length) {
8            int sign = 1;
9            if (i > 0 && expression[i-1] == '-') {
10                sign = -1;
11            }
12            int j = i;
13            while (j < expression.Length && expression[j] != '/' ) j++;
14            int a = int.Parse(expression.Substring(i, j - i)) * sign;
15            i = j + 1; j = i;
16            while (j < expression.Length && expression[j] != '+' && expression[j] != '-') j++;
17            int b = int.Parse(expression.Substring(i, j - i));
18            A = A * b + a * B;
19            B = B * b;
20            int g = Gcd(A, B);
21            A /= g;
22            B /= g;
23            i = j;
24        }
25        return A + "/" + B;
26    }
27
28    private int Gcd(int a, int b) {
29        return (b==0) ? a : Gcd(b, a%b);
30    }
31}

Where Gcd is a function to calculate the greatest common divisor between two numbers using Euclidean algorithm.To add and subtract fractions, you first need to convert them into a common denominator (i.e., the Least Common Multiple of their denominators). After that, you can add or subtract the numerator values. Then, you should simplify the result to its smallest form by dividing both the numerator and denominator by their Greatest Common Divisor (GCD). If the output fraction is a whole number, convert it to its fractional form by appending '/1' to the result.

Python:

1
2python
3import fractions
4import re
5
6expression = "5/3+1/3"
7expression = re.sub(r'(?<=[^+-])(?=\b)', '+', expression)
8
9nums = map(fractions.Fraction, expression.split())
10
11print(str(sum(nums))) # => '2/1'

This Python solution first splits the input string into fractions, which are then parsed as fractions.Fraction instances. Then, it calculates the sum of these instances and converts the result back into a string.

JavaScript:

1
2javascript
3function fractionAddition(expression) {
4    expression = expression.replace(/(\d)-/g, '$1+-');
5    let fractions = expression.split('+');
6    let sum = fractions.reduce((a, b) => a + eval(b), 0);
7    let fraction = new Fraction(sum);
8    return fraction.numerator + '/' + fraction.denominator;
9}

This Javascript solution first tidies up the input string by turning '-' into '+-' if it is in the middle of numbers. Then, it splits the input string into fractions, sums these fractions using eval and reduce, and simplifies the result.

Java:

1
2java
3import java.util.*;
4import java.math.*;
5
6public class Solution {
7    public String fractionAddition(String expression) {
8        Scanner sc = new Scanner(expression).useDelimiter("/|(?=[-+])");
9        int numerator = 0, denominator = 1;
10        while (sc.hasNext()) {
11            int num = sc.nextInt(), den = sc.nextInt();
12            numerator = numerator * den + num * denominator;
13            denominator = denominator * den;
14            int g = gcd(numerator, denominator);
15            numerator /= g;
16            denominator /= g;
17        }
18        return numerator + "/" + denominator;
19    }
20
21    private int gcd(int a, int b) {
22        return b > 0 ? gcd(b, a % b) : a;
23    }
24}

This Java solution uses a Scanner to parse the input string into fractions. In each iteration, it uses the mathematical formula for adding fractions to calculate the numerator and denominator of the result, then uses the Euclidean Algorithm to simplify the result.