Как я могу получить длину повторяющейся десятичной дроби? ⇐ Python

[Anonymous]

Я попал на собеседование и вопрос: как получить длину повторяющейся десятичной дроби?

Например

Код: Выделить всё

1/3=0.3333..., it returns 1,
5/7=0.7142857142857143, it returns 6, since 714285 is the repeating decimal.
1/15=0.066666666666666, it returns 1.
17/150=0.11333333333333333, it returns 1. since 3 is the repeating decimal.

И я пытался написать код

Код: Выделить всё

def solution(a, b):
n = a % b
if n == 0:
return 0

mem = []
n *= 10

while True:
n = n % b
if n == 0:
return 0
if n in mem:
i = mem.index(n)
return len(mem[i:])
else:
mem.append(n)
n *= 10

Однако мой код не может пройти все тесты. И временная сложность равна O(n*logn). Как я могу улучшить это и сделать временную сложность O(n)?


Подробнее здесь: https://stackoverflow.com/questions/463 ... ng-decimal