Summary

This is a straight forward coding problem but with a fair amount of details to get right.

Hints

1. No scary math, just apply elementary math knowledge. Still remember how to perform a long division?
2. Try a long division on $$\frac{4}{9}$$ , the repeating part is obvious. Now try $$\frac{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.

Solution

Approach #1 (Long Division) [Accepted]

Intuition

The key insight here is to notice that once the remainder starts repeating, so does the divided result.

$$\begin{array}{rll} 0.16 \\[-3pt] 6 \enclose{longdiv}{1.00}\kern-.2ex \\[-3pt] \underline{0\phantom{.00}} \\[-3pt] 1\phantom{.}0\phantom{0} && \hbox{$\Leftarrow remainder=1$, mark 1 as seen at $position=0$.} \\[-3pt] \underline{\phantom{0}6\phantom{0}} \\[-3pt] \phantom{0}40 && \hbox{$\Leftarrow remainder=4$, mark 4 as seen at $position=1$.} \\[-3pt] \underline{\phantom{0}36} \\[-3pt] \phantom{00}4 && \hbox{$\Leftarrow remainder=4$ was seen before at $position=1$, so the fractional part which is 16 starts repeating at $position=1$ $\Rightarrow$ 1(6).} \end{array}$$

Algorithm

You will need a hash table that maps from the remainder to its position of the fractional part. Once you found a repeating remainder, you may enclose the reoccurring fractional part with parentheses by consulting the position from the table.

The remainder could be zero while doing the division. That means there is no repeating fractional part and you should stop right away.

Just like the question Divide Two Integers, be wary of edge cases such as negative fractions and nasty extreme case such as $$\frac{-2147483648}{-1}$$ .

Here are some good test cases: