HackerRank: Sam and substrings | How can dynamic programming be used in my code?

Question

Given a number as a string, no leading zeros, determine the sum of all integer values of substrings of the string.

Given an integer as a string, sum all of its substrings cast as integers. As the number may become large, return the value modulo 10**9+7.

Example:

n='42'

ans=4+2+42=48

Full problem: https://www.hackerrank.com/challenges/sam-and-substrings

My code:

def substrings(n):
    ans=0
    l=len(n)
    for i in range(l):
        ans+=int(n[i])*(i+1)*((10**(l-i)-1)//9)
    return ans%(10**9+7)

It's currently getting timed out otherwise passing all test cases. Even though the problem category is dynamic programming, I don't understand how it could be used, and I'm not sure what's slowing my code down.

Answer 1

Instead of treating each digit separately, you could compute the answer for each prefix. Similar to how Horner's method is fast for evaluating polynomials. Let's look at an example and how the answer changes when appending another digit:

567
=> 567 + 56 + 5 + 67 + 6 + 7
 = 5*111 + 6*22 + 7*3

5678
=> 5*1111 + 6*222 + 7*33 + 8*4
   (looks like 10 times the previous answer
    plus something extra, let's call that x)
 = (5*111 + 6*22 + 7*3) * 10 + x
 = 5*1110 + 6*220 + 7*30 + x
=> x = 5*1 + 6*2 + 7*3 + 8*4

So just multiply the previous answer by 10 and add that x (after updating that itself).

Use modulo on the intermediate values for efficiency (at least for ans... For x it would be detrimental, as it doesn't grow very large anyway, and the extra modulo would cost more time than it saves).

def substrings(n):
    ans = x = 0
    mod = 10**9 + 7
    for i, digit in enumerate(n, 1):
        x += int(digit) * i
        ans = (ans * 10 + x) % mod
    return ans

Answer 2

You are reducing the final result modulo 10⁹+7, but are storing intermediate results in full, slowing the summation.

Reduce ans as you go:

    ans += int(n[i]) * (i+1) * ((10**(l-i)-1)//9)
    ans %= 10000000007

You'll also need to find creative ways to reduce (10**(l-i)-1)//9 to more manageable size, for long input strings. Consider writing a function that computes the repdigit 111… modulo M, similar to how pow(a, b, M) is implemented.

We should be able to test that part separately:

def rep_one(n, mod):
    '''
    Compute the number made from N ones, reduced modulo MOD
    >>> rep_one(2, 9)
    2
    >>> rep_one(3, 9) # 111%9 == 3
    3
    >>> rep_one(6, 5) # 111111%6 == 1
    1
    '''
    i = 0
    while n:
        n -= 1
        i = i * 10 + 1
        if i > mod:
            i %= mod
    return i

if __name__ == '__main__':
    import doctest
    doctest.testmod()

We can probably adapt this implementation to retain the intermediate values we're going to need in subsequent iterations of the main loop. Alternatively, reverse the order of the main loop, and combine it with this one (we'll need better variable names, of course).