Leetcode 166: Fraction to Recurring Decimal

https://leetcode.com/problems/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)”.

 

Code

class Solution(object):
    def fractionToDecimal(self, numerator, denominator):
        """
        :type numerator: int
        :type denominator: int
        :rtype: str
        """
        if numerator == 0:
            return "0"
            
        res = ''
        if (numerator < 0) ^ (denominator < 0): # if either or numerator or denominator is negative
            res += "-"
            
        numerator, denominator = abs(numerator), abs(denominator)
            
        quot = numerator / denominator
        res += str(quot)    
        rem = numerator % denominator
        if rem == 0:
            return res
        
        res += "."
        rems = {}     # key is the last remainder and the value is the length of the result
                      # after filled with the quotient of the last remainder * 10 / denominator
        while True:
            rem_new = rem * 10
            quot = rem_new / denominator
            rem_new = rem_new % denominator
            
            if rem_new == 0:
                return res + str(quot) 
                
            if rems.get(rem):
                idx = rems.get(rem)-1
                return res[:idx] + "(" + res[idx:] + ")"
            
            res += str(quot)
            rems[rem] = len(res)
            rem = rem_new
           

 

Idea

We use the basic idea of division to calculate every digit of the result. Besides many corner cases to be considered, the most difficult part is to determine if there is any recurrent part in the result:

I use a dictionary, `rems`, where key is the last remainder and the value is the length of the result after filled with the quotient of the last remainder * 10 / denominator. For example, given numerator=1 and denominator=6, the first digit after the decimal point is 1, which is the quotient of 1*10 by the denominator 6. At this time, we store (1, 3) in `rems` because 1 is the last remainder and 3 is the length of “0.1”. After generating the first digit, we have 4 as the remainder.

The second digit after the decimal point is 6. At this time, we add (4, 4) to `rems` due to the same manner. When we compute the next digit (the third digit after the decimal point), `rem` has set to the last remainder 4. `rem` is checked to be already a key in `rems` (line 34), we conclude we will start to get recurrent quotient(s). Therefore, we start to add parenthesis and output the result.