Fraction to Recurring Decimal


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.


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.

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 performancewise. 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 noncyclic 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 asB = 10^x * 5^y * 2^z * rest
then you addx + 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 onand 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)

@jabberwok said in Fraction to Recurring Decimal:
all reminders
first reminder
which reminder
first reminder
x+y+z remindersremainders
remainder
remainder
remainder
remainders

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, onetwostepping 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), )