Get the sum of each digit below n for how long

Question

This is the code I have, but it is slow to make it faster .. the number range I am on is 123456789, but I cannot get it below 15 seconds and I need it to reach below 5 seconds.

long num = 0; for (long i = 0; i <= n; i++) { num = num + GetSumOfDigits(i); } static long GetSumOfDigits(long n) { long num2 = 0; long num3 = n; long r = 0; while (num3 != 0) { r = num3 % 10; num3 = num3 / 10; num2 = num2 + r; } return num2; } 

sum =(n(n+1))/2 does not give me the results that I need, and are not calculated correctly.

With N = 12, the sum is 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + (1 + 0) + (1 + 1) + (1 + 2) = 51. I need to do this with formulas instead of a loop.

I have about 15 tests to run every 6 seconds.

with parallel, I got one test from 15 seconds to 4-8 seconds.

Just to show you the test I am doing is a tough question.

 [Test] public void When123456789_Then4366712385() { Assert.AreEqual(4366712385, TwistedSum.Solution(123456789)); } 

On my computer, I can run all tests in less than 5 seconds. Look at the photo.

With DineMartine Response, I got the following results:

Answer 1

Your complexity is N log(N) . I found a better algorithm with log(N) complexity. The idea is to iterate over the number of digits, which:

 log10(n) = ln(n)/ln(10) = O(log(n)). 

A demonstration of this algorithm involves a lot of combinatorial calculus. Therefore, I prefer not to write here.

Here is the code:

 public static long Resolve(long input) { var n = (long)Math.Log10(input); var tenPow = (long)Math.Pow(10, n); var rest = input; var result = 0L; for (; n > 0; n--) { var dn = rest / tenPow; rest = rest - dn * tenPow; tenPow = tenPow / 10; result += dn * (rest + 1) + dn * 45 * n * tenPow + dn * (dn-1) * tenPow * 5 ; } result += rest * (rest + 1) / 2; return result; } 

Now you will solve the problem in a split second.

The idea is to write the input as a list of numbers:

Assuming that the solution is given by the function f, we look for g recursive expression f over n:

Actually g can be written as follows:

If you find h, the problem will be practically resolved.

Answer 2

A bit curtailed, but time reaches practical zero:

  private static long getSumOfSumOfDigitsBelow(long num) { if (num == 0) return 0; // 1 -> 1 ; 12 -> 10; 123 -> 100; 321 -> 100, ... int pow10 = (int)Math.Pow(10, Math.Floor(Math.Log10(num))); long firstDigit = num / pow10; long sum = 0; var sum999 = getSumOfSumOfDigitsBelow(pow10 - 1); var sumRest = getSumOfSumOfDigitsBelow(num % pow10); sum += (firstDigit - 1)*(firstDigit - 0)/2*pow10 + firstDigit*sum999; sum += firstDigit*(num%pow10 + 1) + sumRest; return sum; } getSumOfSumOfDigitsBelow(123456789) -> 4366712385 (80us) getSumOfSumOfDigitsBelow(9223372036854775807) -> 6885105964130132360 (500us - unverified) 

The trick is to avoid repeating the same answer over and over. for example 33:

your approach:

 sum = 1+2+3+4+5+6+7+8+9+(1+0)+(1+1)+(1+2)+ ... +(3+2)+(3+3) 

my approach:

 sum = 10*(0 + (1+2+3+4+5+6+7+8+9)) + 10*(1 + (1+2+3+4+5+6+7+8+9)) + 10*(2 + (1+2+3+4+5+6+7+8+9)) + 3*(3 + (1 + 2 + 3)) 

(1+2+3+4+5+6+7+8+9) -part should only be calculated once. The 0..firstDigit-1 loop can be avoided with n(n-1)/2 -trick. Hope this makes sense.

The complexity is O(2^N) with N counting the number of digits. It looks very bad, but fast enough for your threshold of 5 seconds, even for long-max. Perhaps this algorithm can be converted to something running in O(n) by calling getSumOfSumOfDigitsBelow() only once, but it would look a lot more complicated.

The first optimization step: look at your algorithm;)

---

Returning to this problem after DineMartine's answer:

To further optimize the algorithm, sum999 -part can be replaced by an explicit formula. Let's take some number 9999...9=10^k-1 in the code and replace it accordingly:

 sum(10^k-1) = (9 - 1)*(9 - 0)/2*pow10 + 9*sum999 + 9*(num%pow10 + 1) + sumRest sum(10^k-1) = 36*pow10 + 9*sum999 + 9*(num%pow10 + 1) + sumRest 

sum999 and sumRest same for numbers like 10^k :

 sum(10^k-1) = 36*pow10 + 10*sum(10^(k-1)-1) + 9*(num%pow10 + 1) sum(10^k-1) = 36*pow10 + 10*sum(10^(k-1)-1) + 9*((10^k-1)%pow10 + 1) sum(10^k-1) = 36*pow10 + 10*sum(10^(k-1)-1) + 9*pow10 sum(10^k-1) = 45*pow10 + 10*sum(10^(k-1)-1) 

We have the definition of sum(10^k-1) and we know sum(9)=45 . And we get:

 sum(10^k-1) = 45*k*10^k 

Updated code:

  private static long getSumOfSumOfDigitsBelow(long num) { if (num == 0) return 0; long N = (int) Math.Floor(Math.Log10(num)); int pow10 = (int)Math.Pow(10, N); long firstDigit = num / pow10; long sum = (firstDigit - 1)*firstDigit/2*pow10 + firstDigit* 45 * N * pow10 / 10 + firstDigit*(num%pow10 + 1) + getSumOfSumOfDigitsBelow(num % pow10); return sum; } 

This is the same algorithm as DineMartine, but expressed in a recursive way (I compared both implementations and yes, I'm sure it is;)). The execution time is reduced to almost zero, and the time complexity O(n) counts the number of digits or O(long(N)) , taking the value.

Answer 3

To increase productivity, you can calculate the amount starting from the largest number.

Let r=n%10 + 1 . Calculate the sum for the last r numbers.

Then note that if n ends with a 9 , then the total can be calculated as 10 * sum(n/10) + (n+1)/10 * 45 . The first term is the sum of all the digits, but the last, and the second is the sum of the last digit.

The function for calculating the total amount will be equal to:

 static long GetSumDigitFrom1toN(long n) { long num2 = 0; long i; long r = n%10 + 1; if (n <= 0) { return 0; } for (i = 0; i < r; i++) { num2 += GetSumOfDigits(n - i); } // The magic number 45 is the sum of 1 to 9. return num2 + 10 * GetSumDigitFrom1toN(n/10 - 1) + (n/10) * 45; } 

Testing:

 GetSumDigitFrom1toN(12L): 51 GetSumDigitFrom1toN(123456789L): 4366712385 

The complexity of the time is O(log n) .

Answer 4

If your system has several processors (or cores), you can significantly speed it up by doing parallel computations.

The following code demonstrates (this is a compiled console application).

The result, when I try to use it in my system (4 cores with a hyperthread), is as follows:

 x86 version: Serial took: 00:00:14.6890714 Parallel took: 00:00:03.5324480 Linq took: 00:00:04.4480217 Fast Parallel took: 00:00:01.6371894 x64 version: Serial took: 00:00:05.1424354 Parallel took: 00:00:00.9860272 Linq took: 00:00:02.6912356 Fast Parallel took: 00:00:00.4154711 

Please note that the parallel version is about 4 times faster. Also note that the x64 version is much faster (due to the use of long in calculations).

The code uses Parallel.ForEach along with Partitioner to split the range of numbers into reasonable regions by the number of processors available. It also uses Interlocked.Add() to quickly add numbers with effective locking.

I also added another method when you need to pre-calculate the sums for numbers from 0 to 1000. You only need to pre-calculate the amounts once for each program run. See FastGetSumOfDigits() .

Using FastGetSumOfDigits() more than doubles the previous fastest time on my PC. You can increase the SUMS_SIZE value to a larger multiple of 10 to increase speed even further due to space. Increasing it to 10,000 on my PC reduced the time to ~ 0.3 s

(the sums array must be a short array to save space. It does not need a larger type.)

 using System; using System.Collections.Concurrent; using System.Diagnostics; using System.Linq; using System.Runtime.CompilerServices; using System.Threading; using System.Threading.Tasks; namespace Demo { internal class Program { public static void Main() { long n = 123456789; Stopwatch sw = Stopwatch.StartNew(); long num = 0; for (long i = 0; i <= n; i++) num = num + GetSumOfDigits(i); Console.WriteLine("Serial took: " + sw.Elapsed); Console.WriteLine(num); sw.Restart(); num = 0; var rangePartitioner = Partitioner.Create(0, n + 1); Parallel.ForEach(rangePartitioner, (range, loopState) => { long subtotal = 0; for (long i = range.Item1; i < range.Item2; i++) subtotal += GetSumOfDigits(i); Interlocked.Add(ref num, subtotal); }); Console.WriteLine("Parallel took: " + sw.Elapsed); Console.WriteLine(num); sw.Restart(); num = Enumerable.Range(1, 123456789).AsParallel().Select(i => GetSumOfDigits(i)).Sum(); Console.WriteLine("Linq took: " + sw.Elapsed); Console.WriteLine(num); sw.Restart(); initSums(); num = 0; Parallel.ForEach(rangePartitioner, (range, loopState) => { long subtotal = 0; for (long i = range.Item1; i < range.Item2; i++) subtotal += FastGetSumOfDigits(i); Interlocked.Add(ref num, subtotal); }); Console.WriteLine("Fast Parallel took: " + sw.Elapsed); Console.WriteLine(num); } private static void initSums() { for (int i = 0; i < SUMS_SIZE; ++i) sums[i] = (short)GetSumOfDigits(i); } [MethodImpl(MethodImplOptions.AggressiveInlining)] private static long GetSumOfDigits(long n) { long sum = 0; while (n != 0) { sum += n%10; n /= 10; } return sum; } [MethodImpl(MethodImplOptions.AggressiveInlining)] private static long FastGetSumOfDigits(long n) { long sum = 0; while (n != 0) { sum += sums[n % SUMS_SIZE]; n /= SUMS_SIZE; } return sum; } static short[] sums = new short[SUMS_SIZE]; private const int SUMS_SIZE = 1000; } } 

Answer 5

The sum of the digits for 0..99999999 is 10,000,000 * 8 * (0 + 1 + 2 + ... + 9). Then, calculating the remainder (100000000..123456789) using the loop can be quite fast.

For N = 12: The sum of the digits for 0..9 is 1 * 1 * 45. Then use your loop for 10, 11, 12.

With N = 123: The sum of the digits for 0..99 is 10 * 2 * 45. Then use your loop for 100..123.

Do you see the template?

Answer 6

Another approach you can try:

• Convert number to string and then to Char array
• Sum the ASCII codes for all characters, minus the code for 0

Code example:

 long num = 123456789; var numChars = num.ToString().ToCharArray(); var zeroCode = Convert.ToByte('0'); var sum = numChars.Sum(ch => Convert.ToByte(ch) - zeroCode);