3
$\begingroup$

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)?

$\endgroup$
5
  • 1
    $\begingroup$ +1 for showing your code. Looking for repeats in that sequence of remainders is, indeed, the key. Presumably the $\log(n)$ factor comes from searching within the list of previous remainders. And that can be eliminated by restructuring the code according to the answers to the linked question. Write the denominator in the form $2^a5^bq$ with $\gcd(q,10)=1$. Then all you need to do is to look for the smallest positive number $r$ such that $10^r\equiv1\pmod q$. $\endgroup$ – Jyrki Lahtonen Sep 24 '17 at 8:20
  • $\begingroup$ Anyway, this question has been handled many times on our site. There may be other threads that help you even more. You are, of course, welcome to disagree with my choice. I used this search. You can try your luck with a more refined one. $\endgroup$ – Jyrki Lahtonen Sep 24 '17 at 8:24
  • 2
    $\begingroup$ I'm not convinced this is an exact duplicate: the linked question and its answers don't make more than a few vague remarks concerning an algorithm to find the period (divisor of $\phi(n)$, but hard to compute), let alone investigate its time complexity. $\endgroup$ – user436658 Sep 24 '17 at 8:26
  • $\begingroup$ Are you sure your code gives the correct answer for solution(1,1)? $\endgroup$ – Hagen von Eitzen Sep 24 '17 at 9:39
  • $\begingroup$ @HagenvonEitzen, Hi, sir, solution(1, 1)=0. $\endgroup$ – GoingMyWay Sep 24 '17 at 10:35
1
$\begingroup$

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.
$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Mathworld links to a result stating that finding the order of an element of a (black box) group is at least as hard as factoring. $\endgroup$ – Jyrki Lahtonen Sep 24 '17 at 12:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.