It's dp problem. Let F(x) is the sum of digits of numbers 0 through x. answer = F(B) — F(A — 1). x = a[n — 1] * 10 ^ (n — 1) + ... + a[1] * 10 + a[0]. i.e. a[i] is i-th digit of number x. Let D(pos, digSum, constructedPrefixIsEqualToPrefixX) is answer to question "in how many ways we can put digits on positions 0, 1, ... pos, so the sum of digits is equal to digSum.

int dp[10][100][2];

int D(int pos, digSum, constructedPrefixIsEqualToPrefixX) {
	if (digSum < 0)
		return 0;
	if (pos == -1)
		return digSum == 0;
	int &res = dp[pos][digsum][constructedPrefixIsEqualToPrefixX];
	if (res != -1)
		return res;
	res = 0;
	int maxDigit = 9;
	if (constructedPrefixIsEqualToPrefixX)
	    maxDigit = a[pos];
	for (int digit = 0; digit <= maxDigit; ++digit)
		res += D(pos - 1, digSum - digit, constructedPrefixIsEqualToPrefixX && digit == a[pos]);
	return res;
}

misunderstood

http://pastebin.com/2jjauTrm