# Ninja and Mathematics

Posted: 23 Jan, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

#### 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
``````
Approach 1

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’.