DigitDP.cpp

// DigitDP variation for calculating the sum of digits - CPCRC1C on SPOJ
// Code inspired by GeeksforGeeks - coded by adist98
// Given two integers a and b. The task is to print
// sum of all the digits appearing in the
// integers between a and b
#include "bits/stdc++.h"
using namespace std;

// Memoization for the state results
long long int dp[20][180][2];

// Stores the digits in x in a vector digit
long long int getDigits(long long int x, vector <long long int> &digit)
{
	while (x)
	{
		digit.push_back(x%10);
		x /= 10;
	}
}

// Return sum of digits from 1 to integer in
// digit vector
long long int digitSum(int idx, long long int sum, int tight,
						vector <long long int> &digit)
{
	// base case
	if (idx == -1)
	return sum;

	// checking if already calculated this state
	if (dp[idx][sum][tight] != -1 && tight != 1)
		return dp[idx][sum][tight];

	long long ret = 0;

	// calculating range value
	int k = (tight)? digit[idx] : 9;

	for (int i = 0; i <= k ; i++)
	{
		// caclulating newTight value for next state
		int newTight = (digit[idx] == i)? tight : 0;

		// fetching answer from next state
		ret += digitSum(idx-1, sum+i, newTight, digit);
	}

	if (!tight)
	dp[idx][sum][tight] = ret;

	return ret;
}

// Returns sum of digits in numbers from a to b.
long long int rangeDigitSum(long long int a, long long int b)
{
	// initializing dp with -1
	memset(dp, -1, sizeof(dp));

	// storing digits of a-1 in digit vector
	vector<long long int> digitA;
	getDigits(a-1, digitA);

	// Finding sum of digits from 1 to "a-1" which is passed
	// as digitA.
	long long int ans1 = digitSum(digitA.size()-1, 0, 1, digitA);

	// Storing digits of b in digit vector
	vector<long long int> digitB;
	getDigits(b, digitB);

	// Finding sum of digits from 1 to "b" which is passed
	// as digitB.
	long long int ans2 = digitSum(digitB.size()-1, 0, 1, digitB);

	return (ans2 - ans1);
}

// driver function to call above function
int main()
{
	int a,b;
	while(true){
        cin >> a >> b;
        if(a == -1 && b == -1){
            break;
        }
        cout << rangeDigitSum(a, b) << endl;
	}
	return 0;
}