Project Euler #40: Champernowne's constant

Sort by

recency

|

22 Discussions

|

  • + 1 comment

    100% python

    # Enter your code here. Read input from STDIN. Print output to STDOUT
    
    #count of n digit numbers
    fac = [ i*9*10**(i-1) for i in range(1,18)]
    
    #aggregate of the first 1 to n digit number
    fac1 = [fac[0]]
    
    for i in range(1,len(fac)):
        fac1.append(fac[i] + fac1[i-1])
       
    #print(fac, fac1) 
    def find_digit(n):
        if n < 9:
            return(n)
        for j in range(len(fac1)):
            if n == fac1[j]:
                return(9)
            if n < fac1[j]:
                break
        n, r = (n - fac1[j-1])//(j+1), (n - fac1[j-1])%(j+1)
        #if remainder r == 0 , then this is the last digit of the n-1 number
        n = n-1 if r == 0 else n
        #if 190 is question it is first digit of 100(first 3 digit number) i.e 1 
        return(int(str(10**j+n)[j if r == 0 else r-1]))
        
    for a0 in range(int(input())):
        n = map(int, input().split())
        prod = 1
        for i in n:
            prod *= find_digit(i)
        print(prod)
    
        
    
    • + 0 comments

      The divmod() function could have saved you a little work there, and computed faster.

  • + 0 comments

    Lovely challenge 100 points/- python 3

    def index_finder(index):
        i=1
        while True:
            index+=-(9*10**(i-1))*i
            if index<=0:
                index+=(9*10**(i-1))*i
                break
            i+=1
    
        l=(index-1)//i
        ans=str(10**(i-1)+l)[index-l*i-1]
        return int(ans)
    
    for _ in range(int(input())):
        prod=1
        for i in input().split():
            prod*=index_finder(int(i))
        print(prod)
        
    
  • + 0 comments

    I used more math than programming in this question.

    def formposicaodig(x):
        '''
        How many digits are there up to the first digit of x
        (x-10^(n-1))*n + [sum 9*(10^(k-2))*(k-1), from k = 2 to n]
        = (x-10**(n-1))*n + n * 10**(n-1) + (1 - 10**n)//9
        '''
        n = len(str(x))
    
        return 1 +  (x-10**(n-1))*n + n * 10**(n-1) + (1 - 10**n)//9
    
    def formInvposicaodig(pos):
        '''
        x = The position digit 'pos' is contained in which number
        n = len(str(x)) : Number of digits in x
        x = ( pos + (10**n  -1)//9 - n * 10**(n-1) -1) / n + 10**(n-1) 
        return : What is the nth digit of Champernowne's constant
        '''
        n = len(str(pos))
        xcalc = (pos + (10**n-1)//9 - 1) // n
        # As I don't know the number of digits of x, 
        # I iterate until the xcal found is equal to the size of the formula to determine it.
        while n != len(str(xcalc)):
            n = len(str(xcalc))
            xcalc = (pos + (10**n-1)//9 - 1) // n
        return int(str(xcalc)[pos - formposicaodig(xcalc)])
    
    
    n = int(input())
    for k in range(n):
        prd = 1
        for j in map(int,input().split()):
            nth = formInvposicaodig(j)
            if nth == 0:
                prd = 0
                break
            else:
                prd *= nth
        print(prd)
    
  • + 0 comments

    C# even a near constant solution need to reduce the calls to Console.WriteLine to pass the last 3 cases.

  • + 1 comment

    My python solution was timing out for the last two, but when I was testing it on my own computer it passed 10^5 cases in less than 2 seconds. It was reading the input that was taking too long. This made the difference:

    import sys

    input = sys.stdin.readline

    • + 0 comments

      Reading the Input is the main problem making TLE on test cases. First Read the input and store it. Then only try to work on the values. It would be best in general programming to avoid these cases.