C++ | gcd + lcm | beats 100%
Complexity\n- Time complexity: O(n)\n Add your time complexity here, e.g. O(n) \n\n- Space complexity: O(n)\n Add your space complexity here, e.g. O(n) \n\n# Co
# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\n    struct frac_t {\n        int above;\n        int below;\n    };\n\n    void getFracs(vector<frac_t> &fracs, string &expr) {\n        int N = expr.length();\n        int idx = 0;\n        int sign = 1;\n\n        frac_t frac;\n        int digit = 0;\n        while (idx < N) {\n            if (isdigit(expr[idx])) {\n                digit = digit * 10 + (expr[idx] - \'0\');\n            }\n            else if (expr[idx] == \'/\') {\n                frac.above = sign * digit;\n                digit = 0;\n                sign = 1;\n            }\n            else {\n                frac.below = sign * digit;\n                fracs.push_back(frac);\n\n                digit = 0;\n                sign = expr[idx] == \'+\' ? 1 : -1;\n            }\n\n            ++idx;\n        }\n\n        /* Add last frac to fracs */\n        frac.below = sign * digit;\n        fracs.push_back(frac);\n    }\n\n    void addFrac(frac_t &result, frac_t toAdd) {\n        if (result.below == 0) {\n            result = toAdd;\n            return ;\n        }\n\n        /* Get the least common multiple */\n        int below_lcm = lcm(result.below, toAdd.below);\n        result.above *= below_lcm / result.below;\n        toAdd.above *= below_lcm / toAdd.below;\n\n        /* Update result */\n        result.above += toAdd.above;\n        result.below = below_lcm;\n    }\n\npublic:\n    string fractionAddition(string expression) {\n        vector<frac_t> fracs;\n        getFracs(fracs, expression);\n\n        /* Frac Addition */\n        frac_t result(0, 0);\n        for (frac_t frac : fracs) {\n            addFrac(result, frac);\n        }\n\n        /* Simplify the result */\n        if (result.above == 0) {\n            return "0/1";\n        }\n\n        /* Greatest common divisor */ \n        int result_gcd = gcd(result.above, result.below);\n        result.above /= result_gcd;\n        result.below /= result_gcd;\n\n        return to_string(result.above) + "/" + to_string(result.below);\n    }\n};\n```
['Math', 'String', 'Simulation', 'C++']