Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

592. Fraction Addition and Subtraction

Time: $O(n)$

Space: $O(1)$

			


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, 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);
  }
};




			


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, 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);
  }
}




			


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)