Ayush and Expression

Moderate
0/80
Average time to solve is 25m
2 upvotes
Asked in companies
GrofersMicrosoftCityMall

Problem statement

Ayush read about irreducible fractions in the school and made an expression ‘EXPRESSION’ of fraction addition and subtraction.

Note: 
An irreducible fraction is a fraction in which the numerator and denominator are integers that have no other common divisors than 1.

Example: 2/3, 8/9, 0/1 are irreducible fractions, where 8/12, 9/12 are not irreducible fractions.

Expression ‘EXPRESSION’ contains integers from '0' to '9', and characters '/', '+' and '-'.

Each fraction will be an irreducible fraction and will be in the format of ±(numerator/denominator).

Ayush does not know how to solve the expression he made, so he gave you the expression to solve. Your task is to solve the expression.

Note: 
Ayush expects your answer to be an irreducible fraction, so if your answer is an integer, convert it into an irreducible fraction by putting 1 in the denominator.

For example, if your answer is "9", then print "9/1" (without quotes).
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’, denoting the number of test cases. 

The first line of each test case contains a string ‘EXPRESSION’, representing the expression that you need to solve.
Note: 
The input only contains valid irreducible fractions, where the numerator and denominator of each fraction will always be in the range [1,10].
Output format: 
For each test case, return the irreducible fraction after solving the expression.

Output for each test case is printed on a separate line.
Note: 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 5
1 <= |EXPRESSION| <= 10^5

‘EXPRESSION’ will only contain integers from '0' to '9', and characters '/', '+' and '-'. 

Time Limit: 1 sec
Sample Input 1:
2
1/2+3/4
7/3-5/2
Sample Output 1:
 5/4
 -1/6
Explanation 1:
For the first test case, 
The first fractional part is 1/2, and the second fractional part is 3/4.
Lcm of denominators of both the fractional part is 4. Hence, solving the expression would give: 
(1*2)/(2*2) + 3/4 = (2+3)/4 = 5/4, so you need to return 5/4.

For the second test case, 
The first fractional part is 7/3. The second fractional part is 5/2.
Lcm of denominators of both the fractional part is 6. Hence, solving the expression would give:
(7*2)/(3*2) + (5*3)/(2*3) = (14-15)/6 = -1/6, so you need to return -1/6
Sample Input 2:
2
6/5+3/5+1/5
5/3+2/5-1/2
Sample Output 2:
 2/1
 47/30
Hint

Can you solve this problem by making all denominators equal?

Approaches (2)
Using LCM method

We can use brute force to solve the problem. We can simplify this problem by making all denominators equal. This can be done by finding the least common multiple of all the denominators.

 

First, store the fractions in an array. Then, rewrite the expression such that each fraction will have a common denominator. Now, expression can be easily solved by only solving all the numerators. After that, convert the final expression into an irreducible fraction.

 

Algorithm:

 

  • First, extract all the fractions with a sign and store them in an array let’s say ‘ARR’. A fraction can be found by splitting ‘EXPRESSION’ based on ‘+’ and ‘-’ characters, which can be done by finding the next  ‘+’ or ‘-’ character in the STR, and the string between that will be the fraction.
    • For example, if ‘EXPRESSION’ = 1/2-3/4 from index 0 in ‘EXPRESSION’ the next ‘+’ or ‘-’ character is at index 3 so from substring [0, 3) is a fraction. Similarly, the next fraction between indices [3,6] will be -3/4.
  • Consider we have an ‘N’ number of fractions {F1, F2, F3,..., Fn}, which have corresponding numerators {N1, N2, N3, ..., Nn} and denominators {D1, D2, D3, ..., Dn}.
  • Consider a variable ‘LCM’ initialized with value = 1, which is the least common multiple of all the denominators.
  • We can rewrite our expression in the form of
    • Fi = ((LCM / Di) * Ni) / LCM, here Ni = (LCM / Di) * Ni, and Di = LCM.
  • After that, we will add all the numerators and store them in a variable ‘X’, and denominator ‘Y’ = LCM.
  • After that, our final expression will be X / Y. Convert the final expression into an irreducible fraction. To convert into irreducible fraction find GCD of numerator and denominator, then divide both by GCD.
Time Complexity

O(N * log(X)), where ‘N’ is the length of the expression and, ‘X’ is the maximum possible value of the denominator.

 

Since we are iterating over an expression S of length N. In every iteration, we extract a fraction part and find the least common multiple (LCM) of its denominator with the previously occurred denominators. using the Euclidean GCD algorithm. Euclidean GCD algorithm takes O(log(X)) So overall time complexity will be O(N * log(X)).

Space Complexity

O(N), where ‘N’ is the length of the expression. 

 

Since we are using an array of size ‘N’ to store the fractions the space complexity will be O(N).

Code Solution
(100% EXP penalty)
Ayush and Expression
Full screen
Console