# How to (efficiently) compute the sum of the digits of evey number lying between two given numbers?

Given two integers A and B , how to efficiently compute the sum of all the digits of every number int the set $\{N | A \le N \le B \}$.

For example: A = 100 and B = 777, then the required answer is 8655.

I am interested in deriving an formula/efficient algorithm for the same.

-

You should find the formula $f(n)$ for the sum of digits for numbers from 1 to n, then do $f(B)-f(A)$. It is not very clean. The sum of digits of all k digit numbers, that is from $10^{(k-1)} \text { to } 10^k-1$, is $45*(10^k-1)/9$. Stopping part way is harder, but you can do it by recursion. If you want the sum of digits of numbers up to 7655, say, you can do sum of digits up to 999, plus 1000*6*5/2 (for the thousands digits up through 6) + 6*sum of digits up to 999 (for the last three digits for 1000 through 6999) + 7*656 (for the thousands in the 7s) + sum of digits up to 655. The last has one less digit, so you just call your subroutine with that.

-
+1, seems a feasible approach but I haven't understood it fully,could you explain in lucid manner ? – Quixotic Nov 2 '10 at 14:27
If you look at the answer to math.stackexchange.com/questions/8576/… you will see a more detailed explanation for the total number of digits in the n digit numbers. Then you have to deal with the partial decade. Do you have a specific question on that? – Ross Millikan Nov 2 '10 at 15:31
There's more information in Sloane's A037123. – Charles Jun 3 '11 at 3:32

Code in C++

#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
long long  b,i,x,v,c,ans,anc;
int j,k,a[20];
main(){

// freopen("a.in","r",stdin);
//  freopen("a.out","w",stdout);

cin>>b;
k=0; x=1; j=0;
while(b!=0) {a[k]=b%10; b/=10; k++;} for (i=1; i<k; i++) x*=10; if (k==0) x=0; //cout<<x<<" ";
k--;
while(x!=0) {
v=45*(x/10)*k;
c=(a[k]*(a[k]-1)/2)*x+v*a[k]+a[k];
ans+=j*a[k]*x+c; j+=a[k];
x/=10; k--;

}  //cout<<ans<<" ";
ans-=j;

cin>>b;
k=0; x=1; j=0;
while(b!=0) {a[k]=b%10; b/=10; k++;} for (i=1; i<k; i++) x*=10; //cout<<x;
k--;
while(x!=0) {
v=45*(x/10)*k; //cout<<"v=="<<v<<" ";
c=(a[k]*(a[k]-1)/2)*x+v*a[k]+a[k]; //cout<<"c=="<<c<<" ";
anc+=j*a[k]*x+c;  j+=a[k]; //cout<<"anc=="<<anc<<" ";
x/=10; k--; //cout<<endl;

}

cout<<anc-ans;

}

-
Your code seems to work fine on my machine, but perhaps you could add an explanation as to why it works? – Douglas S. Stones Dec 22 '12 at 8:47
Also FYI, this question appears to be a Spoj contest problem (see this). – Douglas S. Stones Dec 22 '12 at 8:50

Just summing them altogether first would produce a number that has the same digit-sum as stringing them altogether.

For example: 101-103

101, 102, 103 -> 1+0+1+1+0+2+1+0+3 -> 9

101+102+103 = 306 = 3+0+6 = 9

Use the Gauss method to add the numbers quickly... That is, if I have the numbers in a set like 1-10 1+2+3+4+5+6+7+8+9+10 = 1+10+2+9+3+8+4+7+5+6 = (1+10)+(2+9)+(3+8)+(4+7)+(5+6) = (11)+(11)+(11)+(11)+(11) = 11*(10/2) <--- 10 is the upper-limit of the given range.

Then add the digits together by dividing by 10 and adding the remainder to one storing variable. (ex. 52 = 5+2 = 7.... 52 --> 52/10 --> 5r2... "2"+? .... 5/10 = 0r5 --> "2"+"5" = 7.)

-