ParshuParishram's blog

By ParshuParishram, history, 3 years ago, In English

Suppose you are given following problem:

Problem Statement: Find the count of numbers between L to R which have sum of digits = x
where, $$$1 \le L \le R \le 10^{18}$$$ and $$$1\le x\le 100$$$

Naive Solution: Check each of the number satisfying the condition and increment the count

Digit DP Solution:
Lets denote the count from L to R as $$$f(L,R)$$$
Then, the problem can be again rewritten as $$$f(L,R) = f(0,R) - f(0,L-1)$$$

Now the problem is to find $$$f(0,R)$$$ for any R
From the constraints of the problem statement you might have guessed that one of the dp states would be the sum of digits i.e. $$$x$$$ but what is the second state?
Its the number of digits!!
For now lets forget about the constraint that the numbers should be $$$\le R$$$
Just think we have upto $$$N$$$ digits and sum of digits should be $$$x$$$. And count that!

$$$dp[N][x]$$$ denotes the count of numbers which have sum of digits $$$=x$$$ and number of digits $$$\le N$$$
Then, $$$dp[N][x] = \sum_{k=0}^{9} dp[N-1][x-k]$$$

All good??
Alright! Moving ahead!

Now, this dp counts the number without the constraint $$$\le R$$$.
Suppose $$$R = 4258$$$ and $$$x=11$$$
Then, we should not count $$$4430$$$ because $$$4430\ge 4258$$$, but how our dp will know we are exceeding R?

We can include one more state or two $$$dp$$$ arrays $$$dp_1$$$ and $$$dp_2$$$
$$$dp_1[N][x] = $$$ count of the numbers under tight constraint
$$$dp_2[N][x] = $$$ count of the numbers with no constraint as such (so $$$dp_2$$$ will behave as it is we discussed above)

Now you may be asking what is tight constraint?
Ans: at the $$$N^{th}$$$ digit we will check if this digit is less or equal to the $$$N^{th}$$$ of $$$R$$$
Denote $$$R_N$$$ as Nth digit of R,
Then, $$$dp_1[N][x] = dp_1[N-1][x-R_N] + \sum_{k=0}^{R_N-1} dp_2[N-1][x-k]$$$

And, for $$$dp_2$$$ its already unconstrained so its chill there :)
$$$dp_2[N][x] = \sum_{k=0}^{9} dp_2[N-1][x-k]$$$


  • Vote: I like it
  • +12
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Any Problem Link to submit code