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

    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