Skip to content

592. Fraction Addition and Subtraction 👎

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  string fractionAddition(string expression) {
    istringstream iss(expression);
    char _;
    int a;
    int b;
    int A = 0;
    int B = 1;

    // Init: A / B = 0 / 1
    // A / B + a / b = (Ab + aB) / Bb
    // So, in each round, set A = Ab + aB, B = Bb.
    while (iss >> a >> _ >> b) {
      A = A * b + a * B;
      B *= b;
      const int g = abs(__gcd(A, B));
      A /= g;
      B /= g;
    }

    return to_string(A) + "/" + to_string(B);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public String fractionAddition(String expression) {
    Scanner sc = new Scanner(expression).useDelimiter("/|(?=[+-])");
    int A = 0;
    int B = 1;

    // Init: A / B = 0 / 1
    // A / B + a / b = (Ab + aB) / Bb
    // So, in each round, set A = Ab + aB, B = Bb.
    while (sc.hasNext()) {
      final int a = sc.nextInt();
      final int b = sc.nextInt();
      A = A * b + a * B;
      B *= b;
      final int g = gcd(A, B);
      A /= g;
      B /= g;
    }

    return A + "/" + B;
  }

  private int gcd(int a, int b) {
    return a == 0 ? Math.abs(b) : gcd(b % a, a);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def fractionAddition(self, expression: str) -> str:
    ints = list(map(int, re.findall('[+-]?[0-9]+', expression)))
    A = 0
    B = 1

    for a, b in zip(ints[::2], ints[1::2]):
      A = A * b + a * B
      B *= b
      g = math.gcd(A, B)
      A //= g
      B //= g

    return str(A) + '/' + str(B)