algoadvance

Leetcode 592. Fraction Addition and Subtraction

Problem Statement

Given a string representing an expression of fractions, you need to add and subtract the fractions and return the result in its simplest form.

The input string will contain fractions separated by a ‘+’ or ‘-‘. Each fraction will be in the form a/b, where a and b are integers. The output should also be a fraction in its simplest form.

Clarifying Questions

  1. Input Range: Is it safe to assume that the input string will always be a valid expression with numbers only?
    • Yes, you can assume the input will always be a valid expression of fractions.
  2. Negative Numbers: Can the numerator and/or the denominator be negative, or will we only have negative signs indicating subtraction?
    • Both numerators and denominators can be negative, but generally negative signs will be indicative of subtraction between fractions.

Strategy

  1. Parsing: Parse the string to identify all fractions and their signs.
  2. Common Denominator: Convert all fractions to have a common denominator to facilitate addition and subtraction.
  3. Numerator Sum: Sum up the numerators after they have a common denominator.
  4. Simplify Result: Reduce the resulting fraction to its simplest form using the greatest common divisor (GCD).

Code

Here’s the C++ function to solve this problem:

#include <string>
#include <vector>
#include <sstream>
#include <numeric>

class Solution {
public:
    std::string fractionAddition(std::string expression) {
        std::vector<int> numerators, denominators;
        std::istringstream iss(expression);
        char dummy;
        int num, denom, first_num, first_denom;
        
        // Parsing the expression and generating numerators and denominators
        while (iss >> num >> dummy >> denom) {
            numerators.push_back(num);
            denominators.push_back(denom);
            iss >> dummy;
        }
        
        // Find least common denominator (LCD)
        int lcm = denominators[0];
        for (int d : denominators) {
            lcm = lcm / std::gcd(lcm, d) * d;
        }
        
        // Adjust numerators to the common denominator
        int result_num = 0;
        for (int i = 0; i < numerators.size(); ++i) {
            result_num += numerators[i] * (lcm / denominators[i]);
        }
        
        // Reduce the result fraction
        int g = std::gcd(abs(result_num), lcm);
        result_num /= g;
        lcm /= g;
        
        return std::to_string(result_num) + "/" + std::to_string(lcm);
    }
};

Time Complexity

  1. Parsing: O(n), where n is the length of the input string.
  2. Finding LCM: O(k), where k is the number of fractions.
  3. Adjusting Numerators: O(k), iterating over the fractions.
  4. Simplifying Fraction: O(log(min(result_num, lcm))), for the GCD calculation.

Overall, the time complexity is primarily O(n + k), which should be efficient for reasonable input sizes according to problem constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI