# C++ 12 lines (GCD)

• 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);
}
``````

• @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"

• @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).

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

GCD

How can you come up with such a good idea?

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