CODEWITHSUNDEEP
pythonalgorithm
GoingMyWay
GoingMyWay

Reputation: 17478

How can I get the length of repeating decimal?

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 a 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 that and make its time complexity O(n)?

Upvotes: 2

Views: 1135

Answers (2)

Deontae Hardnett
Deontae Hardnett

Reputation: 1

Based on this rule which I found from Wikipedia: Fractions with prime denominators Main article: Reciprocals of primes A fraction in lowest terms with a prime denominator other than 2 or 5 (i.e. coprime to 10) always produces a repeating decimal. The length of the repetend (period of the repeating decimal segment) of ⁠ 1 / p ⁠ is equal to the order of 10 modulo p. If 10 is a primitive root modulo p, then the repetend length is equal to p − 1; if not, then the repetend length is a factor of p − 1. This result can be deduced from Fermat's little theorem, which states that 10p−1 ≡ 1 (mod p).

The base-10 digital root of the repetend of the reciprocal of any prime number greater than 5 is 9.[8]

If the repetend length of ⁠ 1 / p ⁠ for prime p is equal to p − 1 then the repetend, expressed as an integer, is called a cyclic number.

Here is my code that helps us get the repetend length:

def rep_length(n):

n=abs(n)

quotient_list=[]

if prime_factorization(n) in list([[2],[5]]) or n==1 or prime_factorization(n)==[2,5]:

return 0

#This is the case because only denominators that are powers of 2 or 5 have no repetend length because they don't repeat.

else: #1 as the denominator has no repetend length either.

n2=max([i for i in factorization(n) if i%2==1 and i%5!=0]) #These are all odd numbers not divisible by 5.

Even numbers that #are not exponents of 2 have repetend lengths because they have odd numbers not divisible by 5 as factors. num=1 remainder_list=[]

while 1 not in remainder_list:

num*=10

remainder_list.append(num%n2)

quotient_list.append(num//n2)

return len(remainder_list)

Here is the link to this: https://en.wikipedia.org/wiki/Repeating_decimal#:~:text=A%20fraction%20in%20lowest%20terms,is%20called%20a%20cyclic%20number.

Upvotes: -1

algrid
algrid

Reputation: 5954

Probably the proper way is to follow the math stack exchange link suggested by @Henry. But concerning your code here's my optimized version of it. The key point here is to use dictionary instead of array - the in operation is much faster in this case.

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

    mem = {}
    n *= 10
    pos = 0

    while True:
        pos += 1
        n = n % b
        if n == 0:
            return 0
        if n in mem:
            i = mem[n]
            return pos - i
        else:
            mem[n] = pos
        n *= 10

On my computer for 29/39916801 this code finishes calculations in several seconds.

Upvotes: 3

Related Questions