Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

3 Answers

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.

share|improve this answer
    
+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
add comment

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;

}
share|improve this answer
1  
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
add comment

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.)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.