How can I get the length of repeating decimal?


  • 0
    G

    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?


  • 0
    G

    I want to answer my own question. Since the time complexity of key in dict is O(1). And using dict to store the position is much faster compared with list.

    So here is the code

    def solution(a, b):
        n = a % b
        if n == 0:
            return 0
        
        pos = 0
        mem = {}
        n *= 10
        while True:
            pos += 1
            n = n % b
            if n == 0:
                return 0
            if n in mem:
                return pos - mem[n] 
            else:
                mem[n] = pos
            n *= 10

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.