🎯 Accurate Fraction Addition with GCD Optimization💯
Intuition\nWhen adding fractions, the key challenge is finding a common denominator and then summing the numerators. Simplifying the resulting fraction by divid
# Intuition\nWhen adding fractions, the key challenge is finding a common denominator and then summing the numerators. Simplifying the resulting fraction by dividing both the numerator and denominator by their greatest common divisor (GCD) ensures the answer is in its simplest form.\n\n# Approach\n1. Parsing the Input: Iterate through the input string to extract each fraction. Identify the numerator and denominator, accounting for possible signs (+ or -).\n2. Common Denominator: As fractions are parsed, calculate a common denominator and adjust numerators accordingly to sum them up.\n3. Simplify the Fraction: After summing the fractions, use the GCD to simplify the result.\n4. Return the Result: Format the simplified fraction as a string.\n\n# Complexity\n- Time complexity:\n The time complexity is O(n), where n is the length of the input string, since we need to parse through the string and perform arithmetic operations.\n\n- Space complexity:\nThe space complexity is O(1), since the space used is independent of the input size.\n# Code\n```java []\nclass Solution {\n    private static int gcd(int a, int b) {\n        if (b == 0) return a;\n        return gcd(b, a % b);\n    }\n    public String fractionAddition(String e) {\n        int ne = 0, de = 1,n = e.length(), i = 0;\n        while (i < n) {\n            int sign = e.charAt(i) == \'-\' ? -1 : 1;\n            int num = 0, den = 0;\n            i=(e.charAt(i) == \'-\' || e.charAt(i) == \'+\')?i+1:i;\n            while (i < n && e.charAt(i) >= \'0\' && e.charAt(i) <= \'9\') \n                num = num * 10 + (e.charAt(i++) - \'0\');\n            num *= sign;\n            i++;\n            while (i < n && e.charAt(i) >= \'0\' && e.charAt(i) <= \'9\') \n                den = den * 10 + (e.charAt(i++) - \'0\');\n            ne = ne * den + num * de;\n            de *= den;\n            int gcd = gcd(Math.abs(ne), de);\n            ne /= gcd;\n            de /= gcd;\n        }\n        return ne == 0 ? "0/1" : ne + "/" + de;\n    }\n}\n```\n```python []\nclass Solution:\n    def fractionAddition(self, expression: str) -> str:\n        def gcd(a: int, b: int) -> int:\n            while b:\n                a, b = b, a % b\n            return a    \n        ne = 0  # Numerator\n        de = 1  # Denominator\n        i = 0\n        n = len(expression)\n        while i < n:\n            sign = -1 if expression[i] == \'-\' else 1\n            i += (expression[i] == \'-\' or expression[i] == \'+\')\n            num = 0\n            while i < n and expression[i].isdigit():\n                num = num * 10 + int(expression[i])\n                i += 1\n            num *= sign\n            i += 1 \n            den = 0\n            while i < n and expression[i].isdigit():\n                den = den * 10 + int(expression[i])\n                i += 1\n            ne = ne * den + num * de\n            de *= den\n            g = gcd(abs(ne), de)\n            ne //= g\n            de //= g\n        return "0/1" if ne == 0 else f"{ne}/{de}"\n```\n```C []\nint 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}\nchar* fractionAddition(const char *expression) {\n    static char result[100]; // Allocate a buffer to hold the result\n    int ne = 0;  // Numerator of the result\n    int de = 1;  // Denominator of the result\n    int i = 0, num = 0, den = 0, sign;\n    while (expression[i] != \'\\0\') {\n        sign = (expression[i] == \'-\') ? -1 : 1;\n        if (expression[i] == \'-\' || expression[i] == \'+\') i++;\n        num = 0;\n        while (expression[i] >= \'0\' && expression[i] <= \'9\') \n            num = num * 10 + (expression[i++] - \'0\');\n        num *= sign;\n        i++; // Skip the \'/\' character\n        den = 0;\n        while (expression[i] >= \'0\' && expression[i] <= \'9\') \n            den = den * 10 + (expression[i++] - \'0\');\n        ne = ne * den + num * de;\n        de *= den;\n        int g = gcd(abs(ne), de);\n        ne /= g;\n        de /= g;\n    }\n    if (ne == 0) {\n        sprintf(result, "0/1");\n    } else {\n        sprintf(result, "%d/%d", ne, de);\n    }\n    return result;\n}\n\n\n```\n
['Math', 'String', 'C', 'Rejection Sampling', 'Simulation', 'Python', 'Java', 'JavaScript']