Ninja and Mathematics
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

Question

Ninja and Mathematics

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

Accepted Answer

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:

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

Space Complexity: O(n)Explanation:

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

Time Complexity: O(n)Explanation:

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

Python (3.5)

"""
    Time complexity: O(N2)
    Space complexity: O(N2)

    Where 'N2' is the divisor which is given in input of every test case.
"""
 
def ninjaAndMathematics(n1, n2): 
    # If n1 is zero then return 0 as string.
    if (n1 == 0): 
        return "0"
    
    # String to store the final fractional answer.
    result = ""
    
    # Add "-" sign if needed.
    if ((n1 > 0) ^ (n2 > 0) == True):
        result += "-"
    
    n1 = abs(n1)
    n2 = abs(n2)
         
    # Integral part.
    result += str(n1 // n2)

    n1 %= n2
        
    # If n2 is a divisor of n1, then return result as no fraction will be involved.
    if (n1 == 0):
        return result
    
    # Fractional part.
    result += "."

    # Dictionary to store the last occurence of any number.
    hashMap = {}

    if n1 not in hashMap.keys():
        hashMap[n1] = len(result)

    # Iterate till n1 is not zero.
    while(n1 != 0): 
        n1 *= 10
        result += str(n1 // n2)
        n1 %= n2
        
        # If n1 is found earlier then add the brackets to the answer string.
        if n1 in hashMap.keys():
            index = hashMap[n1]
            result = result[:index] + "(" + result[index:]
            result += ")"
            break
        # If the number n1 is seen first time, then add it to the map.
        else:
            hashMap[n1] = len(result)
      
    # Return the answer string.  
    return result

Java (SE 1.8)

/*
	Time complexity: O(N2)
	Space complexity: O(N2)

	Where 'N2' is the divisor which is given in input of every test case.
*/

import java.util.HashMap;

public class Solution {
    public static String ninjaAndMathematics(int n1, int n2) { 
        // If n1 is zero then return 0 as string.
        if (n1 == 0) {
            return "0";
        }
        
        // String to store the final fractional answer.
        StringBuilder result = new StringBuilder();
        
        // Add "-" sign if needed.
        if((n1 > 0) ^ (n2 > 0) == true) {
            result.append("-");
        }
        
        n1 = Math.abs(n1);
        n2 = Math.abs(n2);
             
        // Integral part.
        result.append(n1 / n2);
        n1 %= n2;

        // If n2 is a divisor of n1, then return result as no fraction will be involved.
        if (n1 == 0) {
            return result.toString();
        }
        
        // Fractional part
        result.append(".");

        // HashMap to store the last occurence of any number.
        HashMap map = new HashMap();

        map.put(n1, result.length());
        
        // Iterate till n1 is not zero.
        while(n1 != 0) {
            n1 *= 10;
            result.append(n1 / n2);
            n1 %= n2;
            
            // If n1 is found earlier then add the brackets to the answer string.
            if(map.containsKey(n1)) {
                int index = map.get(n1);
                result.insert(index, "(");
                result.append(")");
                break;
            }
            // If the number n1 is seen first time, then add it to the map.
            else {
                map.put(n1, result.length());
            }
        }
        // Return the answer string.
        return result.toString();
    }
}

C++ (g++ 5.4)

/*
    Time complexity: O(N2)
    Space complexity: O(N2)

    Where 'N2' is the divisor which is given in input of every test case.
*/

#include 

string ninjaAndMathematics(int n1, int n2) {   
    // If n1 is zero then return 0 as string.
    if (n1 == 0) {
        return "0";
    }
    
    // String to store the final fractional answer.
    string result = "";
    
    // Add "-" sign if needed.
    if((n1 > 0) ^ (n2 > 0) == true) {
        result += "-";
    }
    
    n1 = abs(n1);
    n2 = abs(n2);
         
    // Integral part.
    result += to_string(n1 / n2);
    n1 %= n2;

    // If n2 is a divisor of n1, then return result as no fraction will be involved.
    if (n1 == 0) {
        return result;
    }
    
    // Fractional part.
    result += ".";

    // Map to store the last occurence of any number.
    unordered_map hashMap;

    hashMap[n1] = result.length();

    // Iterate till n1 is not zero.
    while(n1 != 0) {
        n1 *= 10;
        result += to_string(n1 / n2);
        n1 %= n2;
        
        // If n1 is found earlier then add the brackets to the answer string.
        if(hashMap.find(n1) != hashMap.end()) {
            int index = hashMap[n1];

            result.insert(index, "(");

            result += ")";
            
            break;
        }
        // If the number n1 is seen first time, then add it to the map.
        else {
            hashMap[n1] = result.length();
        }
    }
    // Return the answer string.
    return result;
}