40. Hackerrank solution.md

Hackerrank Project Euler #40

Question

Given T test cases, each test case containing 7 integers, , find the value

Constraints:

• 
• 

Solution

e.g. How to determine d(1000)? Since there are 189 digits before 100 and 2889 digits before 1000, we know that the 1000-th digit comes from a three-digit integer, which is 100 + (1000 - 189 - 1) / 3 = 370. Also, (1000 - 189 - 1) % 3 = 0 suggests that d(1000) = 3.

	i	0	1	2	3	...
Range StartNum	a[0]	1	10	100	1000	...
Number of Digits before StartNum	a[1]	0	9	189	2889	...

from operator import mul
from functools import reduce
from bisect import bisect_left

a = [[1],[0]]
while a[1][-1] <= 10 ** 18:
    n = a[0][-1] * 10
    l = len(str(n)) - 1
    cnt = a[1][-1] + l * 9 * 10 ** (l-1)
    a[0].append(n)
    a[1].append(cnt)

def digit(n):
    i = bisect_left(a[1], n) - 1
    l = len(str(a[0][i]))
    q, r = divmod(n - a[1][i] - 1, l)
    return int(str(a[0][i] + q)[r])

T = int(input())
for _ in range(T):
    print(reduce(mul, [digit(int(x)) for x in input().split()]))