### niklasb's blog

By niklasb, 6 years ago, , I wrote a post about how to tackle certain problems on numbers using dynamic programming techniques over at Stack Overflow. This includes tasks like

• "Find the sum of integers X with digit sum S, where X <= Y" (Y given)
• "Find the number of palindromic integers between L and R"
• "Enumerate all integers between L and R that only have digits 4 and 7"
• "Find the probability that an integer X uniformly chosen from the range [L,R] has at least 10 common digits with a given number S"

that can all be solved with a very similar idea. Just in case somebody's interested.  Comments (24)
 » 6 years ago, # | ← Rev. 3 →   Here is another good post
•  » » Nice, I didn't know that one :) And you just added an image instead of an hyperlink.
•  » » » Lol sorry look now!!
 » niklasb please elaborate your following statement under the heading Compute the number f(Y) of integers X with the property X ≤ Y and X is palindromic :If we can count the f(Y) with the additional restriction that all numbers X must have the same digit count as Y, then we can solve the original problem as well...
•  » » You can just iterate over the number of digits, solve the arising subproblems where the number of digits is fixed and add up all the results.
•  » » » @niklasb is my this implementation satisfies your explanation for O(n^4). If not, please suggest corrections. Thank you for your time.Compute the number f(Y) of integers X with the property X ≤ Y and X has the digit sum 60 int d; bool mem; int sum; int len; int f(int i, int sum_so_far, int lo, string cad) { if (i == len) { return (sum_so_far == sum); } if (sum_so_far > sum) { return 0; } int ret = 0; int dig; if (lo) { if (mem[i][sum_so_far]) { return d[i][sum_so_far]; } else { mem[i][sum_so_far] = 1; int r = 0; for (dig = 0; dig <= 9; ++dig) { r += f(i + 1, sum_so_far + dig, lo, cad); } d[i][sum_so_far] = r; return r; } } int limit; limit = cad[i] - '0'; for (dig = 0; dig <= limit; ++dig) { ret += f(i + 1, sum_so_far + dig, (lo || (dig < (cad[i] - '0'))), cad); } return ret; } int solve (int x) { string cad; cad = NumtoString(x); len = cad.length(); memset(d, 0, sizeof(d)); memset(mem, 0, sizeof(mem)); return f(0, 0, 0, cad); } 
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   Your implementation is by the looks of it, but only after you add memoization to the !lo branch as well! I would recommend you not to pass around cad as a parameter of type string, because it might induce unnecessary copying. You could use const string& cad instead.
 » 6 years ago, # | ← Rev. 2 →   This Google query for "spoj" "numbers between" A and B gives quite many SPOJ problems of this type.
•  » » Good observation, I added the query to my Q&A.
 » There is lecture of Petr on Kharkov winter camps. But on Russian.