### sudipta550's blog

By sudipta550, 3 years ago,

Recently I am trying to solve this problem.But i have to explicitly iterate over n-digit number.This is not exactly what we do in digit dp.Please anyone tell me how to get rid of explicit iteration. Is there any error in this code? Please Help...

#include<bits/stdc++.h>
using namespace std;
long long solve(string s) {
int n = s.length();
long long dp[20][2][11];
memset(dp, 0 LL, sizeof(dp));
dp[0][1][0] = 1;
int ans = 0;
for (int i = 0; i < n; i++) {
for (int t = 0; t < 2; t++) {
int d = ((t == 0) ? 9 : (int) s[i] - '0');
for (int digit = 0; digit <= d; digit++) {
int l = (t && (digit == (int)(s[i] - '0')));
for (int p = 0; p <= 9; p++) {
ans += dp[i][t][p];
if (p == digit) {
// ans += dp[i][t][p];
continue;
}
dp[i + 1][l][digit] += dp[i][t][p];
}

}

}
}
long long sum = 0;
for (int i = 0; i <= 9; i++)
sum += (dp[n][1][i] + dp[n][0][i]);
return sum;
}
int main() {
string a;
cin >> a;
a = to_string(stoll(a) - 1);
long long res_a = 0;
string tt = "";
if (stoll(a) >= 0) {
for (int i = 1; i < a.length(); i++) {
tt += '9';
res_a += solve(tt);
}
res_a += solve(a);
} else res_a = -1;
string b;
cin >> b;
long long res_b = 0;
tt = "";
for (int i = 1; i < b.length(); i++) {
tt += '9';
res_b += solve(tt);
}
res_b += solve(b);
cout << res_b - res_a << endl;
}

• 0