count total number of ones in 1...n

f.py

def f(n):
    cache = [0]
    cnt = 0
    for i in xrange(1, n+1):
        remainder = i % 10
        quotient = i / 10
        m = cache[quotient]
        if remainder == 1:
            m = m + 1
        cache.append(m)
        cnt = cnt + m
    return cnt