Geek Answers Handbook

Count the sum of multiple numbers below N with O (1) complexity?

We are given two numbers M and N. We need to calculate the sum of all integers below N, which are divided by M.

Is it possible to solve the complexity of O (1)?

I know that this is a very simple program, and it can be easily executed with a loop. But I was wondering if it is possible to apply some formula or something directly to calculate the sum of numbers that are divisible by M below N.

+6
source share
2 answers

Indeed, there is a solution O (1):

First, perform integer arithmetic to calculate n = N / M n is the number of members in arithmetic progression with the first member and the total difference equal to M

The sum (which comes from the formula for arithmetic progression) then

n * (1 + n) * M / 2

For example, consider N = 23 and M = 5. You get 5 + 10 + 15 + 20, which is equal to 50. A closed form solution is estimated at 4 * 5 * 5/2, which is also equal to 50.

+3
source 
 L:=floor(M/N) M + 2*M + 3*M + ... + L*M = M (1+2+3+4+...+L)

this can be solved by adding wikipedia

 = M*(L*(L+1)/2)

This can be calculated in O (1)

+2
source

More articles:


All Articles