Avinash - 1 year ago 68

C++ Question

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 Source

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 10^{n}-1 (e.g., 0 to 9 (n=1), 0 to 99 (n=2), etc.) Denote the sum of digits of all integers from 10^{n}-1 as S_{n}. For n=1 (0 to 9), this is just 0+1+2+3+4+5+6+7+8+9=45 (9*10/2). Thus S_{1}=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, S_{n}=10S_{n-1}+10^{n-1}S_{1} as a recursive expression. This simplifies to S_{n}=(9n10^{n})/2.

If the upper limit is of the form 10^{n}, the solution is the above S_{n} 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 S_{n}.