Finding the number of integers between 1 and K, who's sum of the digits is a multiple of D

Question

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:

1. Takes as input two numbers: k & d.
2. Defines a counter variable called count, set to the default value of 0.
3. Iterates over all numbers in the given range: 1 to k.
4. If any number the sum of any number in the above range is a multiple of d, then it adds to the counter count by 1.
5. 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.

EDIT:

The actual problem that I am trying to solve can be found here: Digit Sum - DM::OJ

Thank you.

Answer 1

There's probably a more efficient method, but I can't think of one at the moment. A few suggestions, though:

• Why do you have a badly-named variable hello that is only used once? I'd recommend inlining it.
• There's no need for parentheses around the condition for the if statement.
• There's no need to convert the map to a list before finding the sum.
• You could convert the loop into the sum of a generator expression.
• It's probably a good idea to convert your code to have a main function and an if __name__ == '__main__' guard.

Result (not tested):

def perform_calculation(k, d):
    return sum(sum(map(int, str(i))) % d == 0 for i in range(1, k+1))

def main():
    k = int(input())
    d = int(input())

    print(perform_calculation(k, d))

if __name__ == '__main__':
    main()

Answer 2

Solomon has made some excellent review comments. I won’t duplicate those.

If you want it to work for any number up to 10^1000 in under 1 second, you are going to have to get rid of testing every number in range(1,k+1), and the count += 1 counting of each number.

Consider a sum of digits that has to be a multiple of d=7. The first number that satisfies that is 7. To maintain the sum of 7, if we subtract 1 from the digit 7, we have to add one to another digit, such as a leading zero. 0+1,7-1 or 16. If we repeat that, we get 25. Adding 1 to the tens digit and subtracting 1 from the ones digit is the equivalent of simply adding 9. So we can quickly generate a few more values: 34, 43, 52, 61, and 70. Adding 9 again results in 79, who’s digit sum of 16, so we have to stop at 70. Still, that generated a few numbers. Specifically (70-7)/9+1=8 numbers.

14 is the next multiple of 7, and the smallest number with that digit sum is 59. Again, subtracting 1 from the ones digit, and adding 1 to the tens digit is simply adding 9, so we can generate 68, 77, 86, and 95. The next value is 104, who’s digit sum is only 5, so we have to stop at 95.

Can you figure out a way to generate the first number in each series? Can you identify a stopping criteria? If so, you can directly count the number of numbers in that series with:

 count += (last - first) / inc + 1

What about 3 digit numbers? 106 has a digit sum of 7, and 149 has a digit sum of 14.

What other values of inc do you need? Can you add 1 to the hundreds digit and subtract 1 from the ones? How about adding 1 to the hundreds and subtracting 1 from the tens? Any others?

---

The above will speed up the counting by computing series of numbers, and exploiting commonality. But it is getting way to complicated, as you have to break the series into groups by numbers of digits, and you can have up to 10000 digits.

Perhaps a different approach is needed to determine all of the permutations of digits that result in the required sums.

Emphasis on permutations.