Convert Decimal To Irreducible Fraction

Easy
0/40
Average time to solve is 25m
profile
Contributed by
7 upvotes
Asked in companies
HCL TechnologiesMicrosoftHCL Technologies

Problem statement

You are given a real number, 'NUM'. You have to represent this number as an irreducible fraction of the form A/B, where 'A' and 'B' are the numerator and denominator respectively.

A fraction is called irreducible when the greatest common divisor (GCD/HCF) of the numerator and denominator is one.

Example : 
Given 'NUM' : 1.75
Irreducible fraction  can be represented as 7/4.

Note that 14/8 = 1.75 as well, but 14/8 is not an irreducible fraction.
Note : 
In order to preserve precision, the real number will be given to you in the form of two strings : the integer part, and the fractional part. 

The integer part will contain not more than 8 digits, whereas the fractional part will always contain 8 digits.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first input line contains an integer 'T', the number of test cases. 
Then 'T' test cases follow.

For each test case, the only input line contains a real number 'NUM', in the form of two single space-separated strings: the integer part and the fractional part.
Output Format : 
The output for each test case contains two single space-separated integers 'A' and 'B', the numerator and denominator of the irreducible fraction representing 'NUM' respectively.

The output for each test case will be printed in a separate line.
Note : 
You don't need to print anything. It has already been taken care of, just implement the given function.
Constraints : 
1 <= T <= 10^5
0 < NUM < 10^8

Time Limit : 1 sec
Sample Input 1 :
2
1 75000000
20 20000000

Sample Output 1 :

7 4
101 5
Explanation For Sample Input 1 :
Test case 1 :
7/4 = 1.75

Test case 2 :
101/5 = 20.2
202/10 is also equal to 20.2 but it is not an irreducible fraction.
Sample Input 2 :
2
0 36000000
0 00000001

Sample Output 2 :

9 25
1 100000000
Hint

Try to work with the integer and fractional parts separately. That being given, how do you convert this fractional part into an integer? And after doing that and obtaining the fraction, how will you reduce it?

Approaches (1)
Mathematics

Let : intPart(NUM): The integer part of the given number.

fracPart(NUM): The fractional part of the given number.

Let’s convert the fractional part into a fraction of the form A/B, where ‘A’ and ‘B’ are integers. Here is the algorithm :

 

  1. For this we multiply and divide by 10^8. (Remember that the fractional part has exactly 8 digits.) The fractional part has now been converted to an integer, just like the intPart(NUM).
  2. Now, our number can be written as  ((intPart(NUM) * 10^8) + fracPart(NUM)) / 10^8. We have successfully converted our real number into a fraction.
  3. Finally, to make it irreducible, we find the greatest common divisor of the numerator and denominatorn and divide both of them by it.
Time Complexity

O(log(NUM)), where NUM is the given number.

 

We are processing the given strings digit-wise to convert it into integer, and there can be a maximum of log(NUM) digits. Hence, the overall time complexity will be O(log(NUM)).

Space Complexity

O(1)

 

We are not using any extra space. Hence, the overall space complexity will be O(1).

Code Solution
(100% EXP penalty)
Convert Decimal To Irreducible Fraction
Full screen
Console