Good day. So, I need to find the number of integers between 1 and K (inclusive) satisfying the following condition, modulo (10^9)+7:
The sum of the digits in base ten is a multiple of D
Here is my code:
k = int(input()) d = int(input()) count = 0 for i in range(1,k+1): hello = sum(list(map(int,str(i)))) if (hello%d == 0): count += 1 print (count)
Basically, what the above code does is:
- Takes as input two numbers: k & d.
- Defines a counter variable called
count, set to the default value of
- Iterates over all numbers in the given range:
1 to k.
- If any number the sum of any number in the above range is a multiple of
d, then it adds to the counter
- And then, at the end, finally, it outputs the
count, meaning the number of integers between 1 and K, that have their sum of digits as a multiple of D.
Now, this code works just fine, but I am seeking to make it run for any number until 10^10000 in 1 second or less.
The actual problem that I am trying to solve can be found here: Digit Sum - DM::OJ