Add Two Fractions

Easy
0/40
Average time to solve is 10m
profile
Contributed by
4 upvotes
Asked in company
MAQ Software

Problem statement

You’re given two fractions, a/b, and c/d. Your task is to add these two fractions and print this answer in the simplest form.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer 'T', denoting the number of test cases.

The first line of each test case contains four space-separated integers 'a', 'b', 'c', and 'd', as described in the problem statement.
Output Format : 
For each test case, print two space-separated integers 'x' and 'y', where the sum (a/b)+(c/d) = x/y in the simplest form. 

Print the output of each test case in 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 <= 10 ^ 4
1 <= a,b,c,d <= 10 ^ 9
Time Limit: 1 sec

 Where 'T' denotes the number of test cases, 'a', 'b', 'c' and 'd' denote the integers given as input in the problem.
Sample Input 1 :
1
5 7 4 9
Sample Output 1 :
73 63
Explanation of Sample Input 1 :
Sum of 5/7 + 4/9 = 73/63, which is already in its simplest form because we cannot reduce it further.
Sample Input 2 :
1
1 500 2 1500
Sample Output 2 :
1 300
Explanation of Sample Input 2 :
Sum of 1/500 + 2/1500 = 5/1500, which after reducing in simplest form becomes 1/300.
Hint

Basic Mathematics 

Approaches (1)
Mathematics Based Approach

As it is difficult to add fractions with different denominators, we first make them equal and follow the following steps to reach our answer in the simplest form.

 

  • We will start by finding a common denominator by finding the LCM (Least Common Multiple) of the two denominators.
  • To find the LCM we can make use of the relation that LCM(a,b) = (a*b)/gcd(a,b), and to calculate gcd we can make use of the Euclidean Algorithm.
  • Then we will change the fractions to have the same denominator and add both these terms.
  • We will do this by making the denominator of both the fractions to be equal to the LCM and changing the numerator accordingly. We will simply multiply the numerator by the same constant by which the denominator has been multiplied to reach the LCM.
  • For example 1/3 + 1/6, LCM of 3 and 6 is 6. Hence the first fraction(1/3) changes to 2/6, here we can see that we changed our denominator from 3 to 6(multiplied by 2). Hence we’ll simply multiply our numerator by the same constant, which in our case is 2. Therefore our numerator changes from 1 to 2,
  • Now we simply add the numerators once they have the same denominator.
  • Now we have our answer, but how to check if our answer is in the simplest form or not?
  • We do this by reducing our final fraction obtained into its simplest form by dividing both numerator and denominator by their largest common factor.
  • For example a = 8, b =4, c = 24 and d  = 12,
    • We first make both the denominators equal by finding the LCM of 4 and 12 which comes out to be 12.
    • Our new fractions then become 24/12 and 24/12.
    • Now we add them and reach our answer, that is 48/12.
    • Now to get our answer in the simplest form we divide 48 and 12 by their largest common factor that is 12 and we reach our answer of 4/1.
    • We then print 4 1, which is our answer.
Time Complexity

O(log(min(b,d)), where b and d are the denominators of the given two fractions. 

 

This is the time used to calculate the LCM of two numbers using the Euclidean Algorithm. This comes from Fibonacci Numbers. If we observe carefully we can notice a pattern in the steps used for calculating the GCD of two numbers, for the nth step the numbers would be (fib(n), fib(n+1)). Now Fibonacci series is an exponentially growing series where the ratio of nth/(n-1)th term approaches (sqrt(5)-1)/2 which is also called the golden ratio. So we can see that the time complexity of the algorithm increases linearly as the terms grow exponentially hence the time complexity would be log(min(a,b)).

Space Complexity

O(1).

 

Constant space is being used. Hence, the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Add Two Fractions
Full screen
Console