2
$\begingroup$

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.

$\endgroup$
0

3 Answers 3

7
$\begingroup$

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 $7$s) + sum of digits up to $655.$ The last has one less digit, so you just call your subroutine with that.

$\endgroup$
4
  • $\begingroup$ +1, seems a feasible approach but I haven't understood it fully,could you explain in lucid manner ? $\endgroup$
    – Quixotic
    Nov 2, 2010 at 14:27
  • $\begingroup$ 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? $\endgroup$ Nov 2, 2010 at 15:31
  • $\begingroup$ There's more information in Sloane's A037123. $\endgroup$
    – Charles
    Jun 3, 2011 at 3:32
  • $\begingroup$ @Quixotic see this for a part of your solution. geeksforgeeks.org/count-sum-of-digits-in-numbers-from-1-to-n $\endgroup$ Sep 9, 2016 at 5:41
2
$\begingroup$

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;

}
$\endgroup$
2
  • 1
    $\begingroup$ Your code seems to work fine on my machine, but perhaps you could add an explanation as to why it works? $\endgroup$ Dec 22, 2012 at 8:47
  • $\begingroup$ Also FYI, this question appears to be a Spoj contest problem (see this). $\endgroup$ Dec 22, 2012 at 8:50
-1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .