• 17.1%

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

Hint:

1. No scary math, just apply elementary math knowledge. Still remember how to perform a long division?
2. Try a long division on 4/9, the repeating part is obvious. Now try 4/333. Do you see a pattern?
3. Be wary of edge cases! List out as many test cases as you can think of and test your code thoroughly.

https://discuss.leetcode.com/topic/6079/accepted-cpp-solution-with-explainations

Accepted cpp solution, with explainations

https://discuss.leetcode.com/topic/17071/0ms-c-solution-with-detailed-explanations

0ms C++ Solution with Detailed Explanations

Well, the key to this problem is on how to identify the recurring parts. After doing some examples using pen and paper, you may find that for the decimal parts to recur, the remainders should recur. So we need to maintain the remainders we have seen. Once we see a repeated remainder, we know that we have reached the end of the recurring parts and should enclose it with a ). However, we still need to insert the ( to the correct position. So we maintain a mapping from each remainder to the position of the corresponding quotient digit of it in the recurring parts. Then we use this mapping to retrieve the starting position of the recurring parts.

Now we have solved the trickiest part of this problem.

There are some remaining problems to solve to achieve a bug-free solution.

1. Pay attention to the sign of the result;
2. Handle cases that may cause overflow like numerator = -2147483648, denominator = -1 appropriately by using long long;
3. Handle all the cases of (1) no fractional part; (2) fractional part does not recur; and (3) fractional part recurs respectively.

To handle problem 3, we divide the division process into the integral part and the fractional part. For the fractional part, if it does not recur, then the remainder will become 0 at some point and we could return. If it does recur, the method metioned in the first paragraph has already handled it.

Taking all these into considerations, we have the following code, which takes 0 ms :-)

https://discuss.leetcode.com/topic/7699/do-not-use-python-as-cpp-here-s-a-short-version-python-code

Do not use python as cpp, here’s a short version python code

Though python is slow, It is easy to write

and there’s no overflow

https://discuss.leetcode.com/topic/9778/python-solution

Python solution

Idea is to put every remainder into the hash table as a key, and the current length of the result string as the value. When the same remainder shows again, it’s circulating from the index of the value in the table.