Avinash Avinash - 1 month ago 11
C++ Question

Fastest way to find the sum of decimal digits

What is the fastest way to find the sum of decimal digits?
The following code is what I wrote but it is very very slow for range

1 to 1000000000000000000


long long sum_of_digits(long long input) {
long long total = 0;
while (input != 0) {
total += input % 10;
input /= 10;
}
return total;
}

int main ( int argc, char** argv) {
for ( long long i = 1L; i <= 1000000000000000000L; i++) {
sum_of_digits(i);
}
return 0;
}

Answer

I'm assuming what you are trying to do is along the lines of

#include <iostream>
const long long limit = 1000000000000000000LL;
int main () {
   long long grand_total = 0;
   for (long long ii = 1; ii <= limit; ++ii) {
      grand_total += sum_of_digits(i);
   }
   std::cout << "Grand total = " << grand_total << "\n";
   return 0;
}

This won't work for two reasons:

  • It will take a long long time.
  • It will overflow.

To deal with the overflow problem, you will either have to put a bound on your upper limit or use some bignum package. I'll leave solving that problem up to you.

To deal with the computational burden you need to get creative. If you know the upper limit is limited to powers of 10 this is fairly easy. If the upper limit can be some arbitrary number you will have to get a bit more creative.

First look at the problem of computing the sum of digits of all integers from 0 to 10n-1 (e.g., 0 to 9 (n=1), 0 to 99 (n=2), etc.) Denote the sum of digits of all integers from 10n-1 as Sn. For n=1 (0 to 9), this is just 0+1+2+3+4+5+6+7+8+9=45 (9*10/2). Thus S1=45.

For n=2 (0 to 99), you are summing 0-9 ten times and you are summing 0-9 ten times again. For n=3 (0 to 999), you are summing 0-99 ten times and you are summing 0-9 100 times. For n=4 (0 to 9999), you are summing 0-999 ten times and you are summing 0-9 1000 times. In general, Sn=10Sn-1+10n-1S1 as a recursive expression. This simplifies to Sn=(9n10n)/2.

If the upper limit is of the form 10n, the solution is the above Sn plus one more for the number 1000...000. If the upper limit is an arbitrary number you will need to get creative once again. Think along the lines that went into developing the formula for Sn.

Comments