Fraction Addition and Subtraction

Medium

Asked by:

51 views

Topics:

StringsArrays

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.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the fractions contain negative numerators or denominators? If so, how should I handle negative signs and their placement (e.g., -1/2 vs. 1/-2)?
What is the expected format for the input string? Specifically, can there be leading or trailing spaces, or spaces within a fraction (e.g., '1 / 2')?
What is the range of values for the numerators and denominators? Are there any limitations that could lead to integer overflow during calculations?
Should the result be in its simplest form (i.e., reduced to lowest terms)? If so, do you want me to implement a helper function to find the greatest common divisor (GCD)?
What should the output format be? Should it always be a fraction, even if the result is a whole number (e.g., '2/1' instead of '2')?

Brute Force Solution

Approach

The brute force approach involves directly performing the fraction operations as they appear in the input string. We process the fractions one by one, combining each new fraction with the accumulated result from the previous calculations. At the end, we simplify the final fraction to its lowest terms.

Here's how the algorithm would work step-by-step:

Start with the very first fraction in the expression.
For each subsequent fraction, perform the addition or subtraction operation with the current result.
This involves finding a common denominator, adjusting the numerators, and then adding or subtracting the numerators accordingly.
After each operation, update the current result with the new fraction.
Once all fractions have been processed, simplify the final fraction by finding the greatest common divisor (GCD) of the numerator and denominator, and dividing both by the GCD.

Code Implementation

def fraction_addition_subtraction(expression):
    current_numerator = 0
    current_denominator = 1

    index = 0
    while index < len(expression):
        sign = 1
        if index > 0:
            if expression[index] == '+':
                index += 1
            elif expression[index] == '-':
                sign = -1
                index += 1

        numerator_start = index
        while index < len(expression) and expression[index] != '/':
            index += 1
        new_numerator = int(expression[numerator_start:index])
        index += 1
        denominator_start = index
        while index < len(expression) and expression[index] not in ['+', '-']:
            index += 1
            if index == len(expression):
                break

        new_denominator = int(expression[denominator_start:index])

        # Find common denominator and update numerators
        common_denominator = current_denominator * new_denominator
        current_numerator = current_numerator * new_denominator + sign * new_numerator * current_denominator
        current_denominator = common_denominator

    # Simplify the final fraction
    greatest_common_divisor = gcd(abs(current_numerator), current_denominator)
    current_numerator //= greatest_common_divisor
    current_denominator //= greatest_common_divisor

    return str(current_numerator) + '/' + str(current_denominator)

def gcd(number_a, number_b):
    #Euclidean algorithm for greatest common divisor
    while(number_b):
        number_a, number_b = number_b, number_a % number_b

    return number_a

Big(O) Analysis

Time Complexity

O(n * gcd(a,b)) – The algorithm iterates through the input string of n fractions. For each fraction, it performs addition or subtraction with the accumulated result. The cost of each addition/subtraction is dominated by finding the common denominator and simplifying the result by calculating the greatest common divisor (GCD) of the numerator and denominator. If we assume the GCD operation takes gcd(a,b) time where a and b are the numerator and denominator respectively, and we have n fractions, then the overall complexity is O(n * gcd(a,b)).

Space Complexity

O(1) – The algorithm described primarily uses a constant number of variables to store the current result (numerator and denominator) and doesn't create any auxiliary data structures that scale with the input size N, where N represents the length of the input string. Operations like finding common denominators and simplifying fractions are performed in place using a fixed number of variables. Therefore, the auxiliary space required remains constant irrespective of the input string length.

Optimal Solution

Approach

The key is to process the fractions one by one, keeping track of the current result. We simplify the problem by focusing on adding or subtracting a single fraction at each step and then reducing the final result to its simplest form.

Here's how the algorithm would work step-by-step:

Start with a result of zero, which can be thought of as 0/1.
Take the first fraction from the input string.
Combine the current result with this new fraction by either adding or subtracting, depending on the operation in the input.
To add or subtract, find a common denominator for the current result's fraction and the new fraction. Multiply the numerators accordingly so that the values of the fractions remain the same.
Perform the addition or subtraction by adding or subtracting the numerators, and keeping the common denominator.
After each operation, simplify the resulting fraction by finding the greatest common divisor (GCD) of the numerator and denominator and dividing both by the GCD. This ensures the fraction is in its lowest terms.
Repeat this process for all the fractions in the input string.
Once all fractions are processed, return the final simplified result as a fraction string.

Code Implementation

def fraction_addition_and_subtraction(expression):
    current_numerator = 0
    current_denominator = 1
    index = 0
    while index < len(expression):
        sign = 1
        if index > 0:
            if expression[index] == '+':
                index += 1
            elif expression[index] == '-':
                sign = -1
                index += 1

        numerator = 0
        while index < len(expression) and expression[index].isdigit():
            numerator = numerator * 10 + int(expression[index])
            index += 1

        index += 1

        denominator = 0
        while index < len(expression) and expression[index].isdigit():
            denominator = denominator * 10 + int(expression[index])
            index += 1

        # Find the common denominator for addition/subtraction.
        new_numerator = current_numerator * denominator + sign * numerator * current_denominator
        new_denominator = current_denominator * denominator

        # Simplify the resulting fraction.
        greatest_common_divisor = gcd(abs(new_numerator), new_denominator)
        current_numerator = new_numerator // greatest_common_divisor
        current_denominator = new_denominator // greatest_common_divisor

    return str(current_numerator) + '/' + str(current_denominator)

def gcd(numerator_value, denominator_value):
    # Euclidean algorithm to find the greatest common divisor.
    while denominator_value:
        numerator_value, denominator_value = denominator_value, numerator_value % denominator_value

    return numerator_value

Big(O) Analysis

Time Complexity

O(n + log(C)) – The algorithm iterates through the input string of fractions, which takes O(n) time where n is the number of characters in the input string. Within each iteration (addition/subtraction of fractions), the most computationally intensive part is simplifying the fraction using GCD. Calculating GCD using the Euclidean algorithm takes O(log(C)) time, where C is the larger of the numerator and denominator. Since GCD is applied in each iteration, in the worst case it is called n times but GCD is done at the END of each fraction string process, not within the full string process. So, the time complexity becomes O(n + log(C)).

Space Complexity

O(1) – The algorithm's space complexity is O(1) because it uses a fixed number of variables to store the current result (numerator and denominator), and intermediate values during the GCD calculation. The plain English explanation details operations that involve updating variables in place and calculating GCDs which typically utilize a constant amount of memory. No data structures scale with the input size, N (the length of the input string representing the fraction expression). Therefore, the auxiliary space used is constant.

Edge Cases

Case	How to Handle
Empty input string	Return "0/1" if the input string is empty as there is nothing to add or subtract.
Input string contains only whitespace	Return "0/1" if the input string contains only whitespace after trimming.
Input string starts with '/'	The fraction string should be well-formed, so return an error or "0/1" depending on requirements if it starts with a division.
Integer overflow in numerator or denominator	Use long type for numerator and denominator calculations to prevent overflow, and check after calculations if overflow occured.
Zero denominator in an intermediate fraction	Handle the case of a zero denominator appropriately, either by throwing an error or returning a special value, based on problem definition.
Consecutive operators (e.g., '1/2++1/3')	Consider such inputs as invalid, and return an error or "0/1".
Missing numerator or denominator	Consider this malformed input, and return an error or "0/1"
Input string contains non-numeric characters in numerator/denominator	Consider the input as invalid, and return an error or "0/1".

Empty input string

How to Handle:

Return "0/1" if the input string is empty as there is nothing to add or subtract.

Input string contains only whitespace

How to Handle:

Return "0/1" if the input string contains only whitespace after trimming.

Input string starts with '/'

How to Handle:

The fraction string should be well-formed, so return an error or "0/1" depending on requirements if it starts with a division.

Integer overflow in numerator or denominator

How to Handle:

Use long type for numerator and denominator calculations to prevent overflow, and check after calculations if overflow occured.

Zero denominator in an intermediate fraction

How to Handle:

Handle the case of a zero denominator appropriately, either by throwing an error or returning a special value, based on problem definition.

Consecutive operators (e.g., '1/2++1/3')

How to Handle:

Consider such inputs as invalid, and return an error or "0/1".

Missing numerator or denominator

How to Handle:

Consider this malformed input, and return an error or "0/1"

Input string contains non-numeric characters in numerator/denominator

How to Handle:

Consider the input as invalid, and return an error or "0/1".