卖萌的弱渣

I am stupid, I am hungry.

Fraction to Recurring Decimal

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.

Example

  • Given numerator = 1, denominator = 2, return “0.5”.
  • Given numerator = 2, denominator = 1, return “2”.
  • Given numerator = 2, denominator = 3, return “0.(6)”.

Hint

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

Solution

(Fraction-to-Recurring-Decimal.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

class Solution(object):
    def fractionToDecimal(self, numerator, denominator):
        """
        :type numerator: int
        :type denominator: int
        :rtype: str
        """
        if not numerator:
            return "0"
        ret = ""
        if numerator < 0 or denominator < 0:
            ret = "-"
        if numerator <0 and denominator < 0:
            ret = ""

        p = abs(numerator)
        d = abs(denominator)

        ret += str(p/d)
        if p%d == 0:
            return ret
        else:
            ret += "."
        index = 0
        # hash[remain:index of frac]
        hash = dict()
        frac = ""

        # 22/7
        if p > d:
            p = p-d*(p/d)

        # get fraction part
        while p%d not in hash:
            remain = p%d
            if remain == 0:
                break
            # 1/3
            if p < d:
                p = 10*p
            frac += str(p/d)
            p = p-d*(p/d)
            hash[remain] = index
            index += 1
        # p can divide d
        if p%d == 0:
            return ret+frac

        startindex = hash[p%d]
        return ret+frac[0:startindex]+"("+frac[startindex:index]+")"