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:
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
def f(n, m):
re, c = divmod(n,m)
return m*(m-1)/2*re + (c+1)*c/2