Python solution with detailed explanation


  • 0
    G

    Solution

    Fraction to Recurring Decimal https://leetcode.com/problems/fraction-to-recurring-decimal/

    Algorithm

    • There is no scary math - work through an example.
    • Examples - each example gives one unique insight.
    • 0/12
    • 12/0
    • 4/2,-4/2, 4/-2
    • 11/3, -11/3, 11/-3
    • 1/2
    • 4/9
    • 4/333
    • 1/6
    • 1/90
    • The long division API takes x and y as inputs with x > 0, y > 0 and x < y. We maintain a numerator_map such that numerator_map[x] means that the results for numerator x and denominator y begin at index len(result).
    class Solution(object):
        # 1/6, 4/33, 4/3333
        def long_division(self, x, y):
            # x > 0 and y > 0 and x < y
            result, numerator_map = [], {}
            numerator_map[x] = len(result) # Res numerator x at idx len(result)
            while x != 0:
                x = x*10
                result.append(str(x//y))
                x = int(x%y)
                if x in numerator_map:
                    result.insert(numerator_map[x], "(")
                    result.append(")")
                    break
                else:
                    numerator_map[x] = len(result)
            return "".join(result)
        
        def helper(self, x, y):
            result = []
            if x > y:
                result.append(str(x//y) + ".")
                x = int(x%y)
            else:
                result.append("0.")
            remainder = self.long_division(x, y)
            return "".join(result) + remainder
        
        def fractionToDecimal(self, numerator, denominator):
            """
            :type numerator: int
            :type denominator: int
            :rtype: str
            """
            if denominator == 0: # 0/12
                return "NaN"
            elif numerator == 0: # 12/0
                return "0"
            elif numerator%denominator == 0: # 4/2,-4/2, 4/-2
                return str(numerator//denominator)
            else:
                output = self.helper(abs(numerator), abs(denominator))
                return "-" + output if numerator*denominator < 0 else output
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.