How can I get the length of repeating decimal?

Question

I got an interview and the question is how to get the length of repeating decimal?

For example

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.

And I have tried to write Python code

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

However, my code can't pass all tests. And it's time complexity is O(n*logn). How can I improve its time complexity to O(n)?

Answer 1

As you noticed, the important information is the "remainder before we compute the $k$th decimal", let's call it $r_k$; note that $0\le r_k<b$ and $r_1=a\bmod b$. Given $r_k$, we can compute the $k$th decimal $d_k$ and $r_{k+1}$ as $d_k=\lfloor \frac{10 r_k}b\rfloor$ and $r_{k+1}=10 r_k\bmod b=:S(r_k)$. Note that the function $S$ costs $O(1)$ time and no "extra" memory.

Now if $p\ge1$ is the period length and $q\ge0$ the length of the pre-period, then we will have $r_{k+p}=r_k$ for all $k>q$. In particular, $r_{2k}=r_k$ if $k>q$ and $p\mid k$. Note that the first such $k$ is $\le p+q\le b$.

This suggests the following algorithm with $O(b)$ time and $O(1)$ memory (we need variable $k,u,v,p,q$ sufficiently large to store integers in the range $0,\ldots, b-1$):

1. Set $k\leftarrow 0$, $u\leftarrow r_0(=a\bmod b)$, $v\leftarrow r_0$.
2. Set $u\leftarrow S(u)$, $v\leftarrow S(S(v)$, $k\leftarrow k+1$. [Before and after this, $u=r_k$ and $v=r_{2k}$]
3. If $u\ne v$, go to step 2.
4. Set $v\leftarrow r_0$, $q\leftarrow 0$
5. [Now $v=r_q$, $u=r_{q+k}$] If $v\ne u$, set $u\leftarrow S(u)$, $v\leftarrow S(v)$, $q\leftarrow q+1$ and go back to step 5.
6. [Now $q$ is the length of the pre-period] Set $p\leftarrow 0$
7. Set $v\leftarrow S(v)$ and $p\leftarrow p+1$.
8. If $v\ne u$, go back to step 7.
9. Output $q$ as length of pre-period and $p$ as period length, and terminate.

Answer 2

The task is to find the length $\ell$ of the repeating period of decimals in the decimal expansion of a rational number $n/m$.

Without loss of generality we can assume that any common factors of $n$ and $m$ have been cancelled. It is also easy to factor out all the twos and fives, so we can also assume that we can write the denominator in the form $$ m=2^a5^bq $$ with $\gcd(q,10)=1$.

Given all of this, this answer to my duplicate candidate tells us that $\ell$ is the order of $10$ in the group $\Bbb{Z}_q^*$, in other words $\ell$ is the smallest positive integer with the property $$ 10^\ell\equiv1\pmod q. $$ Lagrange's theorem from elementary group theory tells us that $\ell$ is a factor of $\phi(q)$. Finding the order of $10$ in this group is fast, if we know the prime factorization of $\phi(q)$. My quick estimate is that (heavily using square-and-multiply to calculate powers modulo $q$) the algorithm 4.79 in the Handbook of cryptography runs in $\mathcal{O}(\log^2 q)$ time. But that complexity figure assumes the ability to multiply natural numbers $<q$ modulo $q$ in $\mathcal{O}(1)$. Adjust by a factor for that.

If we don't know the factorization of $\phi(q)$, then it's trickier. My guess is that something better than the brute force method (see Hagen's answer) is known even for a black box group. The methods may be non-deterministic - I'm not up to speed with that.