Simple implementation | best explanation | beat 100% complexity || Easy Solution
Problem Overview\nThe problem involves performing arithmetic operations on fractions given as strings. The goal is to add these fractions and simplify the resul
# Problem Overview\nThe problem involves performing arithmetic operations on fractions given as strings. The goal is to add these fractions and simplify the result. The task is to parse the input string to extract the fractions, compute their sum using a common denominator, and return the simplified result.\n\n# Intuition\nThe problem revolves around handling arithmetic operations on fractions represented in a string format. To solve this, we need to:\n\n- Extract Fractions: Parse the input string to extract each fraction\'s numerator and denominator.\n- Manage Denominators: Use a common denominator to sum up all fractions.\n- Simplify the Result: Simplify the resulting fraction using the greatest common divisor (GCD).\n- My initial thought is to treat the input as a series of fraction additions, compute a common denominator to facilitate the addition, and then simplify the result.\n\n## Solution Explanation\n* Parse the Input String:\n  - Handle the input string to extract individual fractions. Each fraction is in the form of numerator/denominator, and we need to handle both positive and negative values.\n\n- Calculate the Common Denominator:\n    - Compute the least common multiple (LCM) of all denominators to convert each fraction to have the same denominator.\n\n- Sum the Fractions:\n  - Adjust the numerators according to the common denominator and sum them up.\n  \n- Simplify the Fraction:\n    - Use the greatest common divisor (GCD) to simplify the resulting fraction.\n- Return the Result:\n - Format the final result as a string in the form of `numerator/denominator`.\nExplanation of Edge Cases and Complexity\n\n# Edge Cases:\n *  All fractions have different denominators, which requires accurate computation of the LCM.\n* Fractions with negative values are handled by parsing and adjusting signs correctly.\n\n# Complexity\n- Time complexity: The solution runs in $O(n)$ time, where $n$ is the length of the string. Parsing the string and computing LCM/GCD are linear in relation to the number of characters.\n\n- Space complexity: The space complexity is $O(1)$ since only a few extra variables are used regardless of the input size.\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    string fractionAddition(string s) {\n        // Vectors to store the numerators and denominators separately\n        std::vector<int> num;\n        std::vector<int> den;\n\n        int i = 0;\n        int n = s.size();\n\n        // If the string does not start with a negative sign, prepend a \'+\' sign\n        if (s[0] != \'-\') {\n            s = "+" + s;\n        }\n\n        // Parse the string to extract numerators and denominators\n        while (i < n) {\n            if (s[i] == \'/\') {\n                // Finding the numerator\n                int j = i - 1;\n                int power = 0;\n                int res = 0;\n\n                // Traverse back to find the numerator before the \'/\' character\n                while (\'0\' <= s[j] && s[j] <= \'9\') {\n                    int num = s[j] - \'0\';\n                    res = num * std::pow(10, power) + res;\n                    j--;\n                    power++;\n                }\n\n                // If the numerator is negative, multiply by -1\n                if (s[j] == \'-\') {\n                    res = res * (-1);\n                }\n                num.push_back(res);\n\n                // Finding the denominator\n                j = i + 1;\n                bool isneg = false;\n\n                // Check if the denominator is negative (which should not occur in a valid fraction)\n                if (s[j] == \'-\') {\n                    isneg = true;\n                }\n                res = 0;\n\n                // Traverse forward to find the denominator after the \'/\' character\n                while (\'0\' <= s[j] && s[j] <= \'9\') {\n                    int num = s[j] - \'0\';\n                    res = res * 10 + num;\n                    j++;\n                }\n\n                // If the denominator was found to be negative, multiply by -1\n                if (isneg) {\n                    res = res * -1;\n                }\n                den.push_back(res);\n            }\n            i++;\n        }\n\n        // Calculate the least common multiple (LCM) of all denominators\n        int lcm = 1;\n        for (auto itr : den) {\n            lcm = itr * lcm;\n        }\n\n        // Calculate the resulting numerator by summing up all numerators after adjusting them to the common denominator\n        int numRes = 0;\n        for (int i = 0; i < num.size(); i++) {\n            numRes = numRes + (lcm / den[i]) * (num[i]);\n        }\n\n        // Find the greatest common divisor (GCD) of the resulting numerator and the LCM (which is now the denominator)\n        int gcdVal = gcd(abs(numRes), lcm);\n        \n        // Simplify the fraction by dividing both the numerator and denominator by their GCD\n        numRes /= gcdVal;\n        lcm /= gcdVal;\n\n        // Return the resulting fraction as a string in the form "numerator/denominator"\n        return std::to_string(numRes) + "/" + std::to_string(lcm);\n    }\n\nprivate:\n    // Function to calculate the greatest common divisor (GCD) using the Euclidean algorithm\n    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```python []\nfrom fractions import Fraction\n\nclass Solution(object):\n    def fractionAddition(self, expression):\n        """\n        :type expression: str\n        :rtype: str\n        """\n        result = Fraction(0, 1)\n        i = 0\n        n = len(expression)\n        \n        while i < n:\n            # Determine the sign of the current fraction\n            sign = 1\n            if expression[i] == \'-\':\n                sign = -1\n                i += 1\n            elif expression[i] == \'+\':\n                i += 1\n            \n            # Extract the numerator\n            j = i\n            while j < n and expression[j].isdigit():\n                j += 1\n            numerator = sign * int(expression[i:j])\n            \n            # Move past the \'/\' character\n            i = j + 1\n            \n            # Extract the denominator\n            j = i\n            while j < n and expression[j].isdigit():\n                j += 1\n            denominator = int(expression[i:j])\n            \n            # Update the result using the current fraction\n            result += Fraction(numerator, denominator)\n            \n            # Move to the next part of the expression\n            i = j\n        \n        # Return the result as a string in the form of "numerator/denominator"\n        return str(result.numerator) + "/" + str(result.denominator)\n\n\n```\n``` Java []\nimport java.math.BigInteger;\n\nclass Solution {\n    public String fractionAddition(String expression) {\n        BigInteger num = BigInteger.ZERO;\n        BigInteger den = BigInteger.ONE;\n        int i = 0;\n        int n = expression.length();\n        \n        while (i < n) {\n            int sign = 1;\n            \n            // Determine the sign of the current fraction\n            if (expression.charAt(i) == \'-\') {\n                sign = -1;\n                i++;\n            } else if (expression.charAt(i) == \'+\') {\n                i++;\n            }\n            \n            // Extract the numerator\n            int j = i;\n            while (j < n && Character.isDigit(expression.charAt(j))) {\n                j++;\n            }\n            BigInteger numerator = new BigInteger(expression.substring(i, j)).multiply(BigInteger.valueOf(sign));\n            \n            // Move past the \'/\' character\n            i = j + 1;\n            \n            // Extract the denominator\n            j = i;\n            while (j < n && Character.isDigit(expression.charAt(j))) {\n                j++;\n            }\n            BigInteger denominator = new BigInteger(expression.substring(i, j));\n            \n            // Calculate the new denominator (LCM of current and new denominator)\n            BigInteger commonDen = den.multiply(denominator).divide(den.gcd(denominator));\n            \n            // Adjust the numerators to the new common denominator and add them\n            num = num.multiply(commonDen.divide(den)).add(numerator.multiply(commonDen.divide(denominator)));\n            den = commonDen;\n            \n            // Move to the next part of the expression\n            i = j;\n        }\n        \n        // Simplify the fraction\n        BigInteger gcd = num.gcd(den);\n        num = num.divide(gcd);\n        den = den.divide(gcd);\n        \n        return num.toString() + "/" + den.toString();\n    }\n}\n\n\n```\n\n``` JavaScript []\n/**\n * @param {string} expression\n * @return {string}\n */\nvar fractionAddition = function(expression) {\n    let num = 0;\n    let den = 1;\n    let i = 0;\n    const n = expression.length;\n    \n    while (i < n) {\n        let sign = 1;\n        \n        // Determine the sign of the current fraction\n        if (expression[i] === \'-\') {\n            sign = -1;\n            i++;\n        } else if (expression[i] === \'+\') {\n            i++;\n        }\n        \n        // Extract the numerator\n        let j = i;\n        while (j < n && isDigit(expression[j])) {\n            j++;\n        }\n        let numerator = sign * parseInt(expression.substring(i, j));\n        \n        // Move past the \'/\' character\n        i = j + 1;\n        \n        // Extract the denominator\n        j = i;\n        while (j < n && isDigit(expression[j])) {\n            j++;\n        }\n        let denominator = parseInt(expression.substring(i, j));\n        \n        // Calculate the new denominator (LCM of current and new denominator)\n        let commonDen = lcm(den, denominator);\n        \n        // Adjust the numerators to the new common denominator and add them\n        num = num * (commonDen / den) + numerator * (commonDen / denominator);\n        den = commonDen;\n        \n        // Move to the next part of the expression\n        i = j;\n    }\n    \n    // Simplify the fraction\n    let gcdValue = gcd(Math.abs(num), den);\n    num /= gcdValue;\n    den /= gcdValue;\n    \n    return `${num}/${den}`;\n};\n\n// Helper function to check if a character is a digit\nfunction isDigit(char) {\n    return char >= \'0\' && char <= \'9\';\n}\n\n// Helper function to compute the greatest common divisor (GCD)\nfunction gcd(a, b) {\n    while (b !== 0) {\n        let temp = b;\n        b = a % b;\n        a = temp;\n    }\n    return a;\n}\n\n// Helper function to compute the least common multiple (LCM)\nfunction lcm(a, b) {\n    return (a * b) / gcd(a, b);\n}\n```
['Array', 'Math', 'String', 'Simulation', 'Python', 'C++', 'Java', 'JavaScript']