592. Fraction Addition and Subtraction

Find 最大共同分母

T: O(n)

S: O(幾個分數數字）

class Solution {
    private record NumObj (int num, int deno){};
    public String fractionAddition(String expression) {
        List<NumObj> list = new ArrayList<>();
        if (expression.charAt(0) != '-') {
            expression = "+" + expression;
        }
        int sign = expression.charAt(0) == '+' ? 1 : -1;
        int start = 1;
        for (int i = 1; i < expression.length(); i++) {
            if (expression.charAt(i) == '+' || expression.charAt(i) == '-') {
                String[] numStr = expression.substring(start, i).split("/");
                NumObj num = new NumObj(sign*Integer.parseInt(numStr[0]), Integer.parseInt(numStr[1]));
                list.add(num);
                start = i+1;
                sign = expression.charAt(i) == '+' ? 1 : -1;
            }
        }
        String[] numStr = expression.substring(start, expression.length()).split("/");
        NumObj num = new NumObj(sign*Integer.parseInt(numStr[0]), Integer.parseInt(numStr[1]));
        list.add(num);

        int finalDeno = 1;
        for (NumObj numObj : list) {
            finalDeno *= numObj.deno;
        }
        int finalNum = 0;
        for (NumObj numObj : list) {
            finalNum += (finalDeno/numObj.deno)*numObj.num;
        }
        int gcd = gcd(Math.abs(finalNum), finalDeno);
        finalNum = finalNum/gcd;
        finalDeno = finalDeno/gcd;

        return finalNum + "/" + finalDeno;
    }
    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a%b);
    }
}

/**

2 6

6 2

2 0

-1 2
1 3


2
3


-3 2 = -1


-22/1233-


+1/3-1/2


 */

Using LCM

T: $O(nlogab)$, log ab -> 求 gcd 的 time, n 是多少個 “分數

S: O(n), 存幾個分數

```java
class Solution {
    public String fractionAddition(String expression) {
        List<Character> signs = new ArrayList<>();
        List<Integer> num = new ArrayList<>();
        List<Integer> deno = new ArrayList<>();

        // first sign needs to handle in specail case!
        if (expression.charAt(0) == '-') {
            signs.add('-');
        } else {
            signs.add('+');
        }
        // first sign needs specail handle, so from i == 1
        for (int i = 1; i < expression.length(); i++) {
            if (expression.charAt(i) == '+' || expression.charAt(i) == '-') {
                signs.add(expression.charAt(i));
            }
        }
        // split +, needs use \\+
        for(String sub : expression.split("(\\+)|(-)")) {
            if (sub.length() > 0) {
                String[] fraction = sub.split("/");
                num.add(Integer.parseInt(fraction[0]));
                deno.add(Integer.parseInt(fraction[1]));
            }  
        }
    
        int lcm = 1;
        for (int i = 0; i < deno.size(); i++) {
            lcm = lcm(lcm, deno.get(i));
        }
        int newNum = 0;
        for (int i = 0; i < deno.size(); i++) {
            int factor = lcm/deno.get(i);
            if (signs.get(i) == '+') {
                newNum += num.get(i)*factor;
            } else {
                newNum -= num.get(i)*factor;
            }
        }
        int resultGCD = gcd(Math.abs(newNum), Math.abs(lcm));
        return newNum/resultGCD + "/" + lcm/resultGCD;
    }
    private int lcm(int a, int b) {
        return a*b/gcd(a, b);
    }
    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a%b);
    }
}

/*
find lcm
case 1:
if numerator is zero -> denominator is 1
*/
```

avoid number overflow

```java
class Solution {
    public String fractionAddition(String expression) {
        List<Character> signs = new ArrayList<>();

        // first sign needs to handle in specail case!
        if (expression.charAt(0) == '-') {
            signs.add('-');
        } else {
            signs.add('+');
        }
        // first sign needs specail handle, so from i == 1
        for (int i = 1; i < expression.length(); i++) {
            if (expression.charAt(i) == '+' || expression.charAt(i) == '-') {
                signs.add(expression.charAt(i));
            }
        }
        // split +, needs use \\+

        // avoid overflow
        int prevNum = 0;
        int prevDeno = 1;
        int i = 0;
        for(String sub : expression.split("(\\+)|(-)")) {
            if (sub.length() > 0) {
                String[] fraction = sub.split("/");
                int num = Integer.parseInt(fraction[0]);
                int deno = Integer.parseInt(fraction[1]);
                // notice this step
                int g = Math.abs(gcd(deno, prevDeno));
                if (signs.get(i) == '+') {
                    prevNum = prevNum*deno/g + num*prevDeno/g;
                } else {
                    prevNum = prevNum*deno/g - num*prevDeno/g;
                }
                prevDeno = deno*prevDeno/g;
                g = Math.abs(gcd(prevDeno, prevNum));
                prevNum /= g;
                prevDeno /= g;
                i++;
            }  
        }
    
        return prevNum + "/" + prevDeno;
    }
    private int lcm(int a, int b) {
        return a*b/gcd(a, b);
    }
    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a%b);
    }
}

/*
find lcm
case 1:
if numerator is zero -> denominator is 1
*/
```