## 592. Fraction Addition and Subtraction

Given a string representing an expression of fraction addition and subtraction, you need to return the calculation result in string format. The final result should be irreducible fraction. If your final result is an integer, say 2, you need to change it to the format of fraction that has denominator 1. So in this case, 2 should be converted to 2/1.

Example 1:

Input:"-1/2+1/2"
Output: "0/1"


Example 2:

Input:"-1/2+1/2+1/3"
Output: "1/3"


Example 3:

Input:"1/3-1/2"
Output: "-1/6"


Example 4:

Input:"5/3+1/3"
Output: "2/1"


Note:

1. The input string only contains '0' to '9', '/', '+' and '-'. So does the output.
2. Each fraction (input and output) has format ±numerator/denominator. If the first input fraction or the output is positive, then '+' will be omitted.
3. The input only contains valid irreducible fractions, where the numerator and denominator of each fraction will always be in the range [1,10]. If the denominator is 1, it means this fraction is actually an integer in a fraction format defined above.
4. The number of given fractions will be in the range [1,10].
5. The numerator and denominator of the final result are guaranteed to be valid and in the range of 32-bit int.

b'
\n\n

## Solution

\n
\n

#### Approach #1 Using LCM[Accepted]

\n

The first obvious step to be undertaken is to split the given string into individual fractions. We split the string based on + and - sign. We store the signs in the order in which they appear in the string in array. Further, after getting the individual fractions, we further split the fractions based on / sign. Thus, we obtain the individual numerator and denominator parts. We store the same in and arrays respectively.

\n

Now, we\'ve got the data ready to be worked upon. In order to see the method we\'ve used in this implementation, we\'ll take an example and understand the way we work on it.

\n

Let\'s say, the given fraction is:

\n

\n\n

\n

We need to equalize all the denominators so as to be able to add and subtract the numerators easily. The nearest value the denominators can be scaled upto is the LCM of all the denominators. Thus, we need to find the LCM of all the denominators and then multiply all the denominators with appropriate integer factors to make them equal to the LCM. But, in order to keep the individual fraction values unchanged, we need to multiply the individual numerators also with the same factors.

\n

In order to find the LCM, we can go as follows. We use the method . Thus, if we can compute the lcm of two denominators, we can keep on repeating the process iteratively over the denominators to get the overall lcm. To find the lcm of two numbers and , we use . For the above example, the turns out to be 6.

\n

Thus, we scale up the denominators to 6 as follows:

\n

\n\n

\n

Thus, we can observe that, the scaling factor for a fraction is given by: , where is the corresponding scaling factor. Note that, . Thus, . Thus, we find out the corresponding scaling factor for each fraction.

\n

After this, we can directly add or subtract the new scaled numerators.

\n

In the current example, we obtain as the result. Now, we need to convert this into an irreducible fraction. Thus, if we obtain as the final result, we need to find a largest factor , which divides both and . Such a number, as we know, is the gcd of and .

\n

Thus, to convert the result , we divide both the numerator and denominator by the gcd of the two numbers to obtain the final irreducible .

\n

Note: A problem with this approach is that we find the lcm of all the denominators in a single go and then reduce the overall fraction at the end. Thus, the lcm value could become very large and could lead to an overflow. But, this solution suffices for the current range of numbers.

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . Euclidean GCD algorithm takes time for finding gcd of two numbers and . Here refers to the number of fractions in the input string and is the maximum possible value of denominator.

\n
• \n
• \n

Space complexity : . Size of , and list grows upto .

\n
• \n
\n
\n

#### Approach #2 Using GCD[Accepted]

\n

Algorithm

\n

We know that we can continue the process of evaluating the given fractions by considering pairs of fractions at a time and continue the process considering the result obtained and the new fraction to be evaluated this time. We make use of this observation, and thus, instead of segregating the signs, numerators and denominators first, we directly start scanning the given strings and operate on the fractions obtained till now whenever a new sign is encountered.

\n

We operate on the pairs of fractions, and keep on reducing the result obtained to irreducible fractions on the way. By doing this, we can reduce the chances of the problem of potential overflow possible in case the denominators lead to a large value of lcm.

\n

We also observed from the last approach, that we need to equalize the denominators of a pair of fractions say:

\n

\n\n

\n

We used a scaling factor of for the first fraction(both numerator and denominator). Here, . For the second fraction, the scaling factor is given by . Here, \$. Thus, instead of finding the lcm and then again determining the scaling factor, we can directly use: , and . Thus, we need to scale the numerators appropriately and add/subtract them in terms of pairs. The denominators are scaled in the same manner to the lcm of the two denominators involved.

\n

After evaluting every pair of fractions, we again reduce them to irreducible fractions by diving both the numerator and denominator of the resultant fraction by the gcd of the two.

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . Euclidean GCD algorithm takes time for finding gcd of two numbers and . Here refers to the number of fractions in the input string and is the maximum possible value of denominator.

\n
• \n
• \n

Space complexity : . Size of list grows upto .

\n
• \n
\n
\n

Analysis written by: @vinod23

\n
'