Ninja and Mathematics

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
11 upvotes
Asked in companies
FacebookAdobeShareChat

Problem statement

Ninja is a genius in mathematics. He got an interview call from MIT. During the interview, the professor asked Ninja a challenging question.

Given two integers 'N1' and 'N2', the professor asked Ninja to find the fraction when the first number i.e 'N1' is divided by the second number i.e 'N2'. If the fractional part is repeating, then the repeating part should be enclosed in parentheses.

For example, if 'N1' is 1 and 'N2' is 3 and when we divide 1 by 3 i.e 1/3, the answer is 0.333... Here 3 is repeated infinite times because the remainder never becomes zero in this problem. As we know the fractional part ( i.e 3 ) is repeating, so we have to enclose the repeating part in parentheses. Therefore, the answer is “0.(3)”.

Ninja is stuck in this problem. Can you help Ninja to crack this interview and get admission in MIT?

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

The first and the only line of each test case contains two single space-separated integers 'N1' and 'N2'.
Output Format : 
For each test case, return the fraction when 'N1' is divided by 'N2'.
Note: 
You don't need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100
-5000  <= N1 , N2 <= 5000 and N2 != 0

Time limit: 1 sec
Sample Input 1 :
2
1 2
2 3
Sample Output 1:
0.5
0.(6)
Explanation for Sample Output 1:
In test case 1, When we divide 1 by 2 i.e 1/2, the answer is 0.5. After that, the remainder becomes zero so we stop the further division. So the answer to this sample test case is “0.5”.

In test case 2, When we divide 2 by 3 i.e 2/3, the answer is 0.666...  Here 6 is repeated infinite times because the remainder never becomes zero in this problem. As we know the fractional part ( i.e 6 ) is repeating, so we have to enclose the repeating part in parentheses. Therefore, the answer to this sample test case is “0.(6)”.
Sample Input 2 :
2
10 5
-1 6
Sample Output 2:
2
-0.1(6)
Explanation for Sample Output 2:
In test case 1, When we divide 10 by 5 i.e 10/5, the answer is 2. After that, the remainder becomes zero so we stop the further division. So, the answer to this sample test case is “2”.

In test case 2, When we divide -1 by 6 i.e -1/6 the answer is -0.16666...  Here 6 is repeated infinite times because the remainder never becomes zero in this division. As we know the fractional part ( i.e 6 ) is repeating, so we have to enclose the repeating part in parentheses. So the answer to this sample test case is “-0.1(6)”.
Hint

Check if the remainder is repeating or not.

Approaches (1)
Remainder Theorm

The idea is to notice that the fractional part repeats only when we have already seen the same remainder before. So, that means we have to store the end index where this repetition starts in some data structure. 

 

We can use Map / HashMap / Dictionary to store the remainder and its associated index while doing division so that whenever the same remainder comes up, we know there is a repeating fraction part.

 

The steps are as follows:

 

  1. We take a string ‘RESULT’ in which we store our result. We first append sign of our resultant number in this string, as we know if anyone among these two numbers is negative, then sign of our resultant number is negative otherwise sign of our resultant number is positive.
  2. We append the integral part of ‘N1’ / ‘N2’ to ‘RESULT’ and then:
    • ‘N1’ = N1 % N2
    • If the remainder is 0 then we simply return our ‘RESULT’.
  3. Now we have to calculate the fractional part:
    • First, we append “.” into our resultant string.
    • Declare a HashMap in which we store the remainder and its associated index. We put ‘N1’ as key and length of the ‘RESULT’ as value.
    • We run a loop while ‘N1’ ! = 0 :
      • ‘N1’ *= 10
      • Append ‘N1’ / ‘N2’ in ‘RESULT’.
      • Update ‘N1’ as ‘N1’ = ‘N1’ % ‘N2’.
      • Check if the current remainder is already present in the HashMap or not. If  HashMap contains the current remainder:
        • Get the index where the repeating fraction part starts.
        • Insert left parentheses into the resultant string ‘RESULT’ at this index.
        • And then add right parentheses at the end of our resultant string ‘RESULT’ and finally, we break the loop.
      • Else put this remainder and current index into the HashMap.
  4. Finally, we return the resultant string ‘RESULT’.
Time Complexity

O(N2), Where ‘N2’ is the divisor which is given in the input.

 

Since each time we divide the number N1 by N2. We know in the worst case there are N2 remainders possible. Hence, the time complexity will be O(N2).

Space Complexity

O(N2), Where ‘N2’ is the divisor which is given in the input. 

 

Since Every time we divide the number by N2. We know in the worst case there are N2 remainders possible and we use HashMap to store all different remainders. Hence, the space complexity will be O(N2).

Code Solution
(100% EXP penalty)
Ninja and Mathematics
Full screen
Console