C++ 12 lines (GCD)


  • 2
    V

    The initial fraction is 0/1 (n/d). We just need to read next fraction (nn/dd), normalize denominators between n/d and nn/dd (using GCD), and add/subtract the numerator (n +/- nn). In the end, we also need to use GCD to make the resulting fraction irreducible.

    int GCD(int a, int b ){ return (b == 0) ? a : GCD(b, a % b); }
    string fractionAddition(string s) {
        int n = 0, d = 1, p = 0, p1 = 0, p2 = 0;
        if (s[0] != '-') s = "+" + s;
        while (p < s.size()) {
            for (p1 = p + 1; s[p1] != '/'; ++p1);
            for (p2 = p1 + 1; p2 < s.size() && s[p2] != '+' && s[p2] != '-'; ++p2);
            auto nn = stoi(s.substr(p + 1, p1 - p - 1)), dd = stoi(s.substr(p1 + 1, p2 - p1 - 1));
            auto gcd = GCD(d, dd);
            n = n * dd / gcd + (s[p] == '-' ? -1 : 1) * nn * d / gcd;
            d *= dd / gcd;
            p = p2;
        }    
        auto gcd = GCD(abs(n), d);
        return to_string(n / gcd) + "/" + to_string(d / gcd);
    }
    

  • 0
    F

    @votrubac
    your solution fails at large numbers, while the "expected output" can properly handle it. Not sure if we should consider this or not.
    "214748364788888899999/1 - 214748364788888899992/1"


  • 0
    V

    @fentoyal the numbers in your test case are larger than C++ long long range. C++ does not have a built-in support for big integers, so having this test case would put C++ developers at a disadvantage.

    I am guessing that the "expected" algorithm is written in Python (or Java).


  • 0
    K

    @votrubac said in C++ 12 lines (GCD):

    GCD

    How can you come up with such a good idea?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.