🌟 | C++ | Java | Python3 | 0ms Beats 100.00% | O(n) | Fraction Addition and Subtraction |
\n---\n\n# Intuition\nThe problem requires adding and subtracting fractions within a given string expression. The key is to process each fraction one by one, ma
#\n---\n\n# **Intuition**\nThe problem requires adding and subtracting fractions within a given string expression. The key is to process each fraction one by one, maintaining a running total as you move through the string.\n\n# **Approach**\nTo solve this problem, initialize the numerator as 0 and the denominator as 1. As you parse through each fraction in the expression, update the running total by computing the sum of the current fraction and the total so far. Normalize the result by dividing both the numerator and the denominator by their greatest common divisor (GCD) to simplify the fraction. Continue this process until all fractions are processed. The final result is the simplified fraction of the total sum.\n\n# **Complexity**\n- **Time Complexity** $$O(n)$$, where $$n$$ is the length of the expression, as each character in the expression is processed once.\n- **Space Complexity** $$O(1)$$, only a few additional variables are used.\n\n# **Code**\n\n```cpp []\nclass Solution {\npublic:\n    string fractionAddition(string expr) {\n        int num{0}, den{1}, n, d;\n        char slash;\n        for (istringstream in(expr); in >> n >> slash >> d; ) {\n            num = num * d + n * den;\n            den *= d;\n            int gcd = std::gcd(abs(num), den);\n            num /= gcd;\n            den /= gcd;\n        }\n        return to_string(num) + "/" + to_string(den);\n    }\n};\n```\n\n```java []\nclass Solution {\n    public String fractionAddition(String expr) {\n        int num = 0, den = 1;\n        for (String s : expr.split("(?=[+-])")) {\n            int gcd = gcd(Math.abs(num * Integer.parseInt(s.split("/")[1]) + Integer.parseInt(s.split("/")[0]) * den), den * Integer.parseInt(s.split("/")[1]));\n            num = (num * Integer.parseInt(s.split("/")[1]) + Integer.parseInt(s.split("/")[0]) * den) / gcd;\n            den = (den * Integer.parseInt(s.split("/")[1])) / gcd;\n        }\n        return num + "/" + den;\n    }\n    \n    private int gcd(int a, int b) {\n        while (b != 0) {\n            int temp = b;\n            b = a % b;\n            a = temp;\n        }\n        return a;\n    }\n}\n```\n\n```python3 []\nclass Solution:\n    def fractionAddition(self, expr: str) -> str:\n        from math import gcd\n        num, den = 0, 1\n        import re\n        for n, d in re.findall(r\'([+-]?\\d+)/(\\d+)\', expr):\n            n, d = int(n), int(d)\n            num = num * d + n * den\n            den *= d\n            g = gcd(abs(num), den)\n            num //= g\n            den //= g\n        return f\'{num}/{den}\'\n```\n\n---\n\n## **If you found this solution helpful, please upvote! \uD83D\uDE0A**\n\n---
['C++', 'Java', 'Python3']