Goldentime: [Leetcode] 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.

For example,

Given numerator = 1, denominator = 2, return "0.5".
Given numerator = 2, denominator = 1, return "2".
Given numerator = 2, denominator = 3, return "0.(6)".

Analysis:

The point of the problem is to determine if the fraction is repeating. At any point, if the remnant reappears, then we know the result is repeating. However, the repeating part may not start from the beginning of the floating part, so we used a hashmap to record the remnant and its location.

Another edge case is the negative number. `-50/8 = -7` in python. Therefore, the solution is to change to the absolute values and to add a sign in the end.

Code:

class Solution(object):
    def fractionToDecimal(self, numerator, denominator):
        """
        :type numerator: int
        :type denominator: int
        :rtype: str
        """
        if numerator * denominator >= 0:
            sign = ''
        else:
            sign = '-'
        
        numerator, denominator = abs(numerator), abs(denominator)
        integer = sign + str(numerator/denominator)
        
        a = numerator % denominator
        floating, index = '', 0
        hmap = {}
        
        while a!= 0 and a not in hmap:
            hmap[a] = index
            tmp_res = a * 10 / denominator
            a = a * 10 % denominator
            floating += str(tmp_res)
            index += 1
        
        if a == 0:
            return integer + '.' + floating if floating != '' else integer
        else:
            idx = hmap[a]
            return integer + '.' + floating[:idx] + '(' + floating[idx:] + ')'

Goldentime

Monday, July 17, 2017

[Leetcode] Fraction to Recurring Decimal

Analysis:

Code:

No comments:

Post a Comment