Last Updated: 23 Jan, 2021

Ninja and Mathematics

Moderate

Asked in companies

Solve now

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?

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

Solve now

Approaches

01 Approach

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:

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.
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’.
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.
Finally, we return the resultant string ‘RESULT’.

Solve now