There is a such question at codewars(http://www.codewars.com) site.

Write a function to do calculation according below formula:

for i from 1 to n, do i % m and return this sum

for example: f(n=10,m=5) //return 20 (1+2+3+5+0+1+2+3+4+0)

actually it is a quite simple algorithm, use python to do it like:

1 2 |
def f(n, m): return sum(i%m for i in range(n+1)) |

and it works very well when m and n are not very large.

But the performance will be very bad once n and m are very large, for example f(123939234234,249453949) and can not pass the test case of codewars.

We have to find out more clever algorithm.

There is a popular story that Gauss, mathematician extraordinaire, had a lazy teacher. The so-called educator wanted to keep the kids busy so he could take a nap; he asked the class to add the numbers 1 to 100.

Gauss approached with his answer: 5050. So soon? The teacher suspected a cheat, but no. Manual addition was for suckers, and Gauss found a formula to sidestep the problem:

It is said that Gauss was just 10 years old at that time.

We can use a illustrator to show the steps of the algorithm which we need to create.

n can be divided by m into x parts, if n<m then x=0

Every sum of x can be calculated by m*(m-1)/2, there is a different with Gauss’ formula, m-1 instead of m+1, that because m % m=0.

Grown bar mean the value of n%m, just use normal Gauss formula to calculate it.

So our algorithm will be very simple.

First, get x=n/m, if n<m the x=0

Second, get c=n%m

At last sum them together: sum=x*(m*(m-1)/2) + (c+1)*c/2

1 2 3 |
def f(n, m): re, c = divmod(n,m) return m*(m-1)/2*re + (c+1)*c/2 |

#### Latest posts by Wang Weiqiang (王维强) (see all)

- snow world - July 6, 2016
- Krita Drawing: Villa at river bank - June 18, 2016
- Drawing by Krita - June 11, 2016

## Leave a Reply