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

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

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.

• It is generally better to ask a new question rather than edit the question, especially the code, after an answer has been posted. Changing the question may cause answer invalidation. Everyone needs to be able to see what the reviewer was referring to. In this case there is no Answer Invalidation, however, we don't explain other peoples code on code review. Please read What to do after the question has been answered. Jan 20 at 21:50

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


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).

• Hi, thanks for the reply. Unfortunately modding ans as the program goes does not work. I think the real tricky part is not making (10**(l-i)-1)//9 crazy big. Jan 19 at 22:21
• I've searched up how to do A mod M where A is very large. The approach is to turn A into a string and cycle through every digit. This does not work because the input string for this problem, n, as an integer can be as large as 2 times 10 to the fifth. I'm not sure if this would be the approach for the function rep_one. Since this problem is under dynamic programming, I'm not even sure if it can be solved without storing past values. I've edited my question to include a solution posted on the discussion section of the problem. Jan 20 at 21:45
• "within the range of standard Python integers" - Surely you know that standard Python integers have unlimited range? (Well, limited by how much memory you have) Jan 21 at 8:04
• I don't know, I'm not even sure there is fixed-width anymore. It's not like in Python 2, where we had the types int and long. If there still is a distinction like that, I think it's now an implementation detail. I think I wouldn't say it like that anyway, though, instead I'd talk about staying under mod. Jan 21 at 8:24
• Increasing the threshold doesn't make it right. I highly doubt multiple comparisons and subtractions are faster than one modulo, btw. Jan 21 at 8:28