Digit DP Problem Help

Hello Everyone.

This was asked to me in an Interview today.

You are given two numbers N and K. Find count of all non - negative integers
 less than N whose sum of digits are divisible by K modulo 10^9 +  7.

N can be very large (Taken as a string).

I think it is a digit DP Problem Can anyone help me with some similar problem or how can we solve this specific problem since I am not familiar with Digit DP.

Thanks in advance. @galencolin @ssrivastava990 @vijju123 @taran_1407

No idea how can we do this using digit dp , can u please help @carre @aryan12 @everule1

Any approach you think in this. Digit DP is just my guess here.

What is constraint on K?

1 Like

K is until 100 and N can be large. I found this on gfg it is here