Algorithm
Problem link- https://www.spoj.com/problems/CPCRC1C/
CPCRC1C - Sum of Digits
Majid is a 3rd-grade elementary student and quite well in mathematics. Once, Majid's teacher asked him to calculate the sum of numbers 1 through n.
Majid quickly answered, and his teacher made him another challenge. He asked Majid to calculate the sum of the digits of numbers 1 through n.
Majid did finally find the solution. Now it is your turn, can you find a solution?
Input
Two space-separated integers 0 <= a <= b <= 109.
Program terminates if a and b are -1.
Output
The sum of the digits of numbers a through b.
Example
Input:
1 10
100 777
-1 -1
Output:
46
8655
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007LL
#define EPS 1e-9
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
const int MAXN = 1e5+5;
string a, b;
ll dp[12][105][2];
int n;
ll solve(string &s, int idx, ll sum, int isPrefixEqual){
if(dp[idx][sum][isPrefixEqual] != -1)
return dp[idx][sum][isPrefixEqual];
ll res = 0;
if(idx == n){
return sum;
}else{
if(isPrefixEqual){
for(int i = 0;i <= s[idx]-'0'; i++){
if(s[idx]-'0' == i)
res += solve(s, idx + 1, sum + i, 1);
else
res += solve(s, idx + 1, sum + i, 0);
}
}else{
for(int i = 0;i <= 9; i++){
res += solve(s, idx + 1, sum + i, 0);
}
}
}
dp[idx][sum][isPrefixEqual] = res;
return res;
}
ll f(string &a){
ll sum = 0;
for(auto c : a){
sum += c - '0';
}
return sum;
}
int main(){
io;
while(1){
cin >> a >> b;
if(a == "-1" && b == "-1")
break;
n = b.size();
memset(dp, -1, sizeof dp);
ll ansR = solve(b, 0, 0, 1);
n = a.size();
memset(dp, -1, sizeof dp);
ll ansL = solve(a, 0, 0, 1);
cout << ansR - ansL + f(a) << endl;
}
return 0;
}Input
1 10
100 777
-1 -1
100 777
-1 -1
Output
46
8655
8655
Demonstration
SPOJ Solution-Sum of Digits-Solution in C, C++, Java, Python