Fraction to Recurring Decimal

(This can be classified under Hash Table too)

Problem

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.

If multiple answers are possible, return any of them.

It is guaranteed that the length of the answer string is less than 10^4 for all the given inputs.

For example:

Input: numerator = 1, denominator = 2
Output: "0.5"

Input: numerator = 2, denominator = 1
Output: "2"

Input: numerator = 2, denominator = 3
Output: "0.(6)"

Input: numerator = 4, denominator = 333
Output: "0.(012)"

Thought Process

• We just have to keep track of the remainders. The moment we see a repeated one (1700 in this example), we stop and ask "when was the first time I saw this remainder?" For this particular example, the answer is "when I was trying to find the 3rd decimal place". Therefore, the recurrence starts from the 3rd decimal place. That's it.

• Using a HashMap to store remainder so that we could know if a same remainder exists

• A HashMap is the best for this question so we can detect a "cycle" with there being repeating remainders. Similar to the Happy Number problem

• (Remainder * 10 / denominator) is what we have for fractional part

Solution

class Solution:
    def fractionToDecimal(self, numerator: int, denominator: int) -> str:
        if denominator == 0:
            return 
        neg = (numerator > 0 and denominator < 0) or (numerator < 0 and denominator > 0)
        res = ""
        
        if neg:
            res+="-"
        
        numerator = abs(numerator)
        denominator = abs(denominator)
        
        if numerator % denominator == 0:
            res+=str(numerator//denominator)
            return res
        
        
        res+=str(numerator//denominator)
        res+="."
        
        r = numerator % denominator #get the initial remainder
        
        dic = {}
        
        while r:
            
            if r in dic:
                res = res[:dic[r]] + '(' + res[dic[r]:] + ')'
                print(dic)
                break
            dic[r] = len(res)
            
            r*=10
            res+=str(r//denominator) #append current decimal 
            r = r % denominator #get the next remainder
           
        
        return res
            
        
        

Time Complexity

• Time: O(denominator) becuase the mod iteration must be less than the denominator, so you can run from 1 to mod times

• Space: O(denominator)