来一道google真题

把所有正数連接起来
比如
12345678910111213141516
问第n位数字除以三余几。
这题目有啥好算法？

return  (n % 3) & 1

A straight-forward brute-force solution.
首先计算出第n个数字属于第几个数。对数字进行观察，有以下特征：
1-9: 共9个数，每个数只有1位
10-99：共90个数，每个数有2位
100-999: 共900个数，每个数有3位
...
以此类推，从10^(n-1)到10^n-1，共9*10^(n-1)个数，每个数有n位
通过这个规律，我们可以用一个循环来寻找n落在哪个区间。
Python:
def find(n):
    digit = 0
    id = 0
    d = 9
    t = 1
    while n > d:
        id += d
        n = n-t*d
        d = d*10
        t = t+1
    id += n/t
    n = n%t
    if n==0:
        digit = int(str(id)[-1])
    esle:
        digit = int(str(id+1)[n-1])
    return digit%3