592. Fraction Addition and Subtraction

MediumMathStringSimulation
Leetcode Link

Problem Description

The problem provides a string expression that represents an expression composed of fractions which need to be added or subtracted. Our goal is to process this expression, perform the arithmetic operations, and return the result as a string formatted as a fraction.

The result must be presented as an irreducible fraction, which means that the numerator and denominator have no common factors other than 1. Furthermore, if the result is an integer, it should be displayed as a fraction with a denominator of 1 (e.g., 2 as an integer should be represented as 2/1).

So, if we have an expression like "-1/2+1/2-1/3", our task is to calculate the result of this expression and simplify it to its lowest terms.

Intuition

To arrive at the solution, we can follow these steps:

  1. Normalize the expression to ensure that all fractions are preceded by a sign (+ or -). This simplifies parsing the string as it guarantees a consistent format for processing.

  2. Iterate over the characters in the expression and parse each fraction one at a time along with its sign.

  3. For each fraction, convert it into an integer numerator with a common denominator (which, in this case, has been chosen as 2520, the least common multiple of the denominators 1 through 10—since the problem only involves fractions with denominators from 1 to 10). By doing this, we can add or subtract all fractions directly without worrying about finding the least common denominator during each operation.

  4. Accumulate the result of these operations in a variable (like x in the solution code), keeping track of the total numerator after applying the signs.

  5. Once all fractions are processed, we find the greatest common divisor (GCD) of the resulting numerator and the common denominator to simplify the fraction to its lowest terms.

  6. Divide both the numerator (x) and the common denominator (y) by the GCD to simplify the fraction.

  7. Format and return the result as a string in the required numerator/denominator format.

The key intuition for solving this problem efficiently is to convert all fractions to have a common denominator, perform the arithmetic operations once, and then simplify the result at the end, rather than simplify after each operation. This reduces the complexity of the problem significantly.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which type of traversal does breadth first search do?

Solution Approach

The implementation uses simple arithmetic and string parsing without any complex data structures. The steps and rationale of the algorithm are explained below:

  1. Initialization: A common denominator y is initialized as 2520, which is the least common multiple (LCM) of the numbers from 1 to 10. This ensures all fractions from the input can be expressed with this common denominator. The variable x is initialized to 0 and will serve as the accumulator for the numerators.

  2. Expression Preprocessing: To ensure consistency for parsing the expression, a + sign is added in front of the expression if the first character is a digit.

  3. Parsing and Walking Through the Expression: The algorithm walks through the expression character by character, with a nested loop to identify each individual fraction and its preceding sign.

    • sign: Determines whether the current fraction should be added or subtracted according to the sign (+ or -) identified.
    • i and j: Serve as pointers. i marks the start of the fraction (or sign), and j finds the end of the fraction by looking for the next operator or the end of the string.

  4. Fraction Handling: Each fraction is broken into its numerator (a) and denominator (b), and its equivalent numerator with the common denominator (y) is computed. This is done by multiplying int(a) * y and dividing by int(b), which rescales the numerator to match the common denominator, and the sign is applied.

  5. Accumulation: The computed numerator for each fraction (considering the sign) is accumulated into our result numerator x.

  6. Simplification: Once all numerators have been summed, the gcd (Greatest Common Divisor) function is used to find the GCD of the result numerator x and common denominator y to simplify the fraction.

  7. Result Formation: Both x and y are divided by their GCD to get the simplified numerator and denominator. The result is then formatted into a string in the form of "x/y", which is the irreducible fraction representation of the original expression.

The function gcd is a mathematical utility function that returns the greatest common divisor of two numbers and is essential for reducing the fraction to its simplest form.

This approach uses a linear scan of the input string which results in an O(n) time complexity where n is the length of the input string. The space complexity of the algorithm is O(1), as it uses a fixed number of variables and no additional data structures that grow with the input size.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Example Walkthrough

Let's break down the solution approach with a small example, the expression "-1/2+1/2+1/3".

Step 1: Initialization

  • Common denominator y is set to 2520.
  • Result numerator x is initialized to 0.

Step 2: Expression Preprocessing

  • There's no need for a + at the start because the expression already starts with a -.

Step 3: Parsing and Walking Through the Expression

  • Start at the first fraction -1/2:
    • sign is - (subtracting this fraction).
    • a (numerator) is -1.
    • b (denominator) is 2.

Step 4: Fraction Handling

  • Convert -1/2 to have a common denominator:
    • int(a) * y / int(b) is equivalent to -1 * 2520 / 2.
    • This equals -1260.

Step 5: Accumulation

  • Sum -1260 into x, so x becomes -1260.

Step 6: Simplification

  • No need to apply until all fractions are processed.

Repeat steps 3 to 5 for +1/2:

  • sign is +.
  • a is 1.
  • b is 2.
  • Convert to common denominator: 1 * 2520 / 2 = 1260.
  • Add to x: -1260 + 1260 = 0.

Repeat steps 3 to 5 for +1/3:

  • sign is +.
  • a is 1.
  • b is 3.
  • Convert to common denominator: 1 * 2520 / 3 = 840.
  • Add to x: 0 + 840 = 840.

Step 6: Simplification

  • Now, find the GCD of x which is 840 and y which is 2520.
  • The GCD is 840.
  • Divide both x and y by 840 to simplify (840/840 and 2520/840).
  • x becomes 1 and y becomes 3.

Step 7: Result Formation

  • The result is 1/3.

So our original expression -1/2+1/2+1/3 simplifies to 1/3 when processed according to the solution approach described. Through common denominators and accumulation, we achieve a simplified final result.

Solution Implementation

1from math import gcd
2
3class Solution:
4    def fraction_addition(self, expression: str) -> str:
5        # Initialize numerator and common denominator
6        numerator, common_denominator = 0, 1
7        for d in range(2, 11):
8            common_denominator *= d  # LCM(1,2,3,4,5,6,7,8,9,10)
9      
10        # Ensure the first character is a sign
11        if expression[0].isdigit():
12            expression = '+' + expression
13      
14        # Process each fraction in the string
15        i, expr_length = 0, len(expression)
16        while i < expr_length:
17            # Determine the sign of the fraction
18            sign = -1 if expression[i] == '-' else 1
19            i += 1  # Move past the sign character
20          
21            # Find the end of the current fraction
22            j = i
23            while j < expr_length and expression[j] not in '+-':
24                j += 1
25          
26            # Extract the current fraction
27            fraction_str = expression[i:j]
28            numerator_str, denominator_str = fraction_str.split('/')
29          
30            # Update the combined numerator
31            numerator += sign * int(numerator_str) * common_denominator // int(denominator_str)
32          
33            # Move to the start of the next fraction
34            i = j
35      
36        # Reduce the fraction by the greatest common divisor
37        common_divisor = gcd(numerator, common_denominator)
38        numerator //= common_divisor
39        common_denominator //= common_divisor
40      
41        # Return the reduced fraction as a string
42        return f'{numerator}/{common_denominator}'
43
1class Solution {
2  
3    // Method to add fractions from the string expression.
4    public String fractionAddition(String expression) {
5        // Initialize numerator and a common denominator which is lcm of 6,7,8,9,10.
6        int numerator = 0, commonDenominator = 6 * 7 * 8 * 9 * 10;
7      
8        // Add '+' to the beginning if the expression starts with a number.
9        if (Character.isDigit(expression.charAt(0))) {
10            expression = "+" + expression;
11        }
12      
13        int i = 0;
14        int lengthOfExpression = expression.length();
15      
16        // Iterate through the characters in the expression.
17        while (i < lengthOfExpression) {
18            // Determine the sign of the term (+1 or -1).
19            int sign = expression.charAt(i) == '-' ? -1 : 1;
20            i++;  // Move past the sign for parsing the number.
21          
22            // Determine the position of the next sign (or end of string).
23            int j = i;
24            while (j < lengthOfExpression && expression.charAt(j) != '+' && expression.charAt(j) != '-') {
25                j++;
26            }
27          
28            // Extract the fraction and split it into numerator and denominator.
29            String fraction = expression.substring(i, j);
30            String[] fractionParts = fraction.split("/");
31            int currentNumerator = Integer.parseInt(fractionParts[0]);
32            int currentDenominator = Integer.parseInt(fractionParts[1]);
33          
34            // Adjust the numerator according to the common denominator and the sign.
35            numerator += sign * currentNumerator * commonDenominator / currentDenominator;
36          
37            // Move the index 'i' to the position of next term's sign or the end of the string.
38            i = j;
39        }
40      
41        // Simplify the fraction by dividing both numerator and denominator by their gcd.
42        int greatestCommonDivisor = gcd(Math.abs(numerator), commonDenominator);
43        numerator /= greatestCommonDivisor;
44        commonDenominator /= greatestCommonDivisor;
45      
46        // Return the result in fraction format as a string.
47        return numerator + "/" + commonDenominator;
48    }
49
50    // Helper method to calculate the Greatest Common Divisor (GCD) using Euclid's algorithm.
51    private int gcd(int a, int b) {
52        return b == 0 ? a : gcd(b, a % b);
53    }
54}
55
1#include <string>
2#include <cstdlib>
3
4class Solution {
5public:
6    // Method to add fractions from the string expression
7    std::string fractionAddition(std::string expression) {
8        // Initialize numerator and common denominator which is lcm of 6, 7, 8, 9, 10
9        int numerator = 0;
10        int commonDenominator = 6 * 7 * 8 * 9 * 10;
11      
12        // Add '+' to the beginning if the expression starts with a number
13        if (isdigit(expression[0])) {
14            expression = "+" + expression;
15        }
16      
17        size_t i = 0;
18        size_t lengthOfExpression = expression.size();
19      
20        // Iterate through the characters in the expression
21        while (i < lengthOfExpression) {
22            // Determine the sign of the term (+1 or -1)
23            int sign = expression[i] == '-' ? -1 : 1;
24            i++;  // Move past the sign for parsing the number
25          
26            // Determine the position of the next sign (or end of string)
27            size_t j = i;
28            while (j < lengthOfExpression && expression[j] != '+' && expression[j] != '-') {
29                j++;
30            }
31          
32            // Extract the fraction and split it into numerator and denominator
33            std::string fraction = expression.substr(i, j - i);
34            size_t slashPosition = fraction.find('/');
35            int currentNumerator = std::stoi(fraction.substr(0, slashPosition));
36            int currentDenominator = std::stoi(fraction.substr(slashPosition + 1));
37          
38            // Adjust the numerator according to the common denominator and the sign
39            numerator += sign * currentNumerator * commonDenominator / currentDenominator;
40          
41            // Move the index 'i' to the position of the next term's sign or the end of the string
42            i = j;
43        }
44      
45        // Simplify the fraction by dividing both numerator and denominator by their GCD
46        int greatestCommonDivisor = gcd(abs(numerator), commonDenominator);
47        numerator /= greatestCommonDivisor;
48        commonDenominator /= greatestCommonDivisor;
49      
50        // Return the result in fraction format as a string
51        return std::to_string(numerator) + "/" + std::to_string(commonDenominator);
52    }
53
54private:
55    // Helper method to calculate the Greatest Common Divisor (GCD) using Euclid's algorithm
56    int gcd(int a, int b) {
57        while (b != 0) {
58            int t = b;
59            b = a % b;
60            a = t;
61        }
62        return a;
63    }
64};
65
1// Function to calculate the Greatest Common Divisor (GCD) using Euclid's algorithm.
2function gcd(a: number, b: number): number {
3    return b === 0 ? a : gcd(b, a % b);
4}
5
6// Function to add fractions from the string expression.
7function fractionAddition(expression: string): string {
8    // Initialize a numerator and a common denominator, which is the LCM of 6, 7, 8, 9, 10.
9    let numerator = 0;
10    const commonDenominator = 6 * 7 * 8 * 9 * 10;
11
12    // Add '+' to the beginning if the expression starts with a number.
13    if (expression.charAt(0).match(/\d/)) {
14        expression = "+" + expression;
15    }
16
17    let i = 0;
18    const lengthOfExpression = expression.length;
19
20    // Iterate through the characters in the expression.
21    while (i < lengthOfExpression) {
22        // Determine the sign of the term (+1 or -1).
23        const sign = expression.charAt(i) === '-' ? -1 : 1;
24        i++; // Move past the sign for parsing the number.
25
26        // Determine the position of the next sign (or end of the string).
27        let j = i;
28        while (j < lengthOfExpression && expression.charAt(j) !== '+' && expression.charAt(j) !== '-') {
29            j++;
30        }
31
32        // Extract the fraction and split it into numerator and denominator.
33        const fraction = expression.substring(i, j);
34        const [currentNumerator, currentDenominator] = fraction.split("/").map(Number);
35
36        // Adjust the numerator according to the common denominator and the sign.
37        numerator += sign * (currentNumerator * commonDenominator) / currentDenominator;
38
39        // Move the index 'i' to the position of the next term's sign or the end of the string.
40        i = j;
41    }
42
43    // Simplify the fraction by dividing both the numerator and denominator by their GCD.
44    const greatestCommonDivisor = gcd(Math.abs(numerator), commonDenominator);
45    numerator /= greatestCommonDivisor;
46    const simplifiedCommonDenominator = commonDenominator / greatestCommonDivisor;
47
48    // Return the result in fraction format as a string.
49    return `${numerator}/${simplifiedCommonDenominator}`;
50}
51
Not Sure What to Study? Take the 2-min Quiz：

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Time and Space Complexity

Time Complexity

The time complexity of the given code is determined by the number of operations related to iterating through the input expression string and the operations involved in computations and finding the greatest common divisor (gcd).

Let n be the length of the input expression.

  1. The code iterates over each character in the expression exactly once, which takes O(n) time.
  2. The split operation on the string s, done inside the while loop, operates on substrings which have a collective length of O(n). However, since the split operation does not depend on the length of the expression but on the number of fractions, and we can consider the number of fractions to be much less than n, we treat each split as O(1).
  3. Multiplication, addition, and integer division operations inside the loop are constant-time operations (O(1)).
  4. The most demanding operation in terms of time complexity is the gcd computation at the end. The gcd of two numbers a and b can be found in O(log(min(a, b))). Considering the constant value of y is much larger than x, we can approximate this step to O(log(y)).

Taking all of these steps into account, and assuming gcd does not significantly vary with respect to n, the overall time complexity of the code is O(n).

Space Complexity

The space complexity is determined by the memory allocated for the variables and any additional structures used by the algorithm.

  1. There are only a constant number of integer variables used (x, y, z, a, b, and a few index holders like i and j), which contribute O(1) space.
  2. The string s that is a substring of the expression is used in split operation. In the worst-case scenario, all fractions in the input string could have the maximum possible length. But since we only store one fraction at a time, its space usage is also O(1).
  3. There are no data structures like arrays or lists dynamically growing with input size.

Hence, the space complexity of this algorithm is O(1) as it uses a constant amount of space regardless of the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫