Fraction to Recurring Decimal


  • 0

    Click here to see the full article post


  • 0
    J

    You can avoid using a map. You don't need all reminders to test for a cycle, you need only the first reminder of the cycle. For example, if you do 1 / 3 result is 0.(3). Now the tricky part - how to figure out which reminder is first in the cycle, because you can have 1 / 6 = 0.1(6), 1 is outside of the cycle. Think that numerator = 10^x * 2^x * 5^z * rest, where x, y, z can be 0. To get the first reminder of the cycle you need to skip x+y+z reminders. It works. This way you skip using HashMap because using HashMap is MAGNITUDES slower than integer operations, this code spends 90% if not more on HashMap calls.


  • 0
    This post is deleted!

  • 0
    G

    @jabberwok Can you explain more details?


  • 0
    O

    I think he is referring to the technique of loop detection that we all know how to do for the question "Find the node where the loop starts for a singly linked list". Basically, try to get reminders two at a time for one and one at a time for another. When they are equal, we detect a loop, etc.


  • 0
    J

    @Geminiiiiii

    I can't read the original article because my subscription ran out, so I can't explain in details what is wrong with it, the only thing I remember that it used HashMap which was a huge overkill performance-wise. My idea was that all fractions are either finite like 0.123 or cyclic like 0.123333...(3) . Cyclic fractions have a part that is not repeated like 0.12 in my example and the part that is getting repeated: 3. So my solution was

    • Determine length of non-cyclic part
    • Now we guaranteed to know the first digit of the cycle
    • Keep dividing until we hit the first digit of the cycle, then compare next known digit with the new digit from the division. Repeat until you either have different digits or you hit the digit you started with. In the first case - continue, in the second case you got a hit.

    The first point was the tricky one so I came up with this formula:

    A / B, where B can be represented as B = 10^x * 5^y * 2^z * rest then you add x + y + z and you get how many digits come before cycle.

    Example:

    1 / 280= 0.003571428571428571428571428571...

    280 = 10^1 * 5^0 * 2^2 * 7

    x + y + z = 1 + 0 + 2 = 3

    It means that the cycle starts at the 4th digit - 5

    0.003571428571428571428571428571
    -----^

    We go forward until we hit 5 and store the index of that position 10 (potential cycle end)

    0.003571428571428571428571428571
    -----------^

    We continue going forward and compare digits: 5, 7, 1, 4, 2, 8

    0.003571428571428571428571428571
    ------------^-----^ and so on

    and we hit the position 10 (potential cycle end) on the left. The loop is closed, we detected a cycle. So the result shall be

    0.003(571428)


  • -1
    J
    This post is deleted!

  • 0

    @jabberwok said in Fraction to Recurring Decimal:

    all reminders
    first reminder
    which reminder
    first reminder
    x+y+z reminders

    remainders
    remainder
    remainder
    remainder
    remainders


  • 0
    J

    @Geminiiiiii @oyugioho

    I managed to find my solution, it is actually easier than the algorithm I described. You don't even need to compare digits, you just need to store the first remainder of the loop and compare current remainder to it. @oyugioho you were right, one-two-stepping would also work, but it will walk over the loop twice.

    class Solution(object):
        def fractionToDecimal(self, numerator, denominator):
            return fractionToDecimal(numerator, denominator)
    
    def digits_before_loop(den):
        n = den
        digits = 0
        while not n % 10:
            n /= 10
            digits += 1
    
        while not n % 5:
            n /= 5
            digits += 1
    
        while not n % 2:
            n /= 2
            digits += 1
    
        return digits
    
    def list_to_str(l):
        return ''.join(str(d) for d in l)
    
    def fractionToDecimal(n, d):
        if d == 0:
            raise ZeroDivisionError()
    
        if n == 0:
            return '0'
    
        if (n < 0) == (d < 0):
            sign = ''
        else:
            sign = '-'
            n = abs(n)
            d = abs(d)
    
        whole_part = str(n / d)
        n = n % d
        if n == 0:
            return sign + whole_part
    
        pre_loop_part = []
        loop_part = []
    
        first_remainder = None
        digits_to_skip = digits_before_loop(d)
        while True:
            if digits_to_skip == 0:
                first_remainder = n
    
            n *= 10
    
            digit = n / d
    
            if digits_to_skip > 0:
                pre_loop_part.append(digit)
            else:
                loop_part.append(digit)
    
            digits_to_skip -= 1
            n = n % d
    
            if first_remainder == n:
                template = '{}{}.{}({})'
                break
    
            if n == 0:
                template = '{}{}.{}{}'
                break
    
        return template.format(
            sign, whole_part, 
            list_to_str(pre_loop_part),
            list_to_str(loop_part),
        )
    

Log in to reply
 

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