Блог пользователя rootn

Автор rootn, история, 7 лет назад, По-английски

In how many ways can you represent a number as the sum of consecutive numbers.

To solve this, we can use the concept of A.P. We know that sum of A.P. is n = (m/2)*(2*a + (m - 1)*d) if n is the sum and m is the number of integers with common difference d in the A.P. In our problem, n is the given number and m is the number of consecutive integers, obviously d is 1. Now we can derive two conclusions from above formula:

  1. Manipulating the above formula as n/m = m/2 + a - 1/2 we can see that n/m is greater than m/2 becausea - 1/2 is always positive as 'a' belongs to the range [1, INF). Therefore, the conclusion is n/m > m/2 => m < sqrt(2n).

  2. Above formula can also be written as a = n/m - m/2 + 1/2.From here we can conclude that n/m - m/2 + 1/2 is an integer as a is integer.

So if we iterate over m from 2 to sqrt(2n) and check for every such m that n/m - m/2 + 1/2 is integer or not. If we count the number of m's for which n/m - m/2 + 1/2 is integer then that count will be the number of ways in which we can represent n as sum of consecutive numbers.

int count = 0;
for(int i = 1;i < sqrt(2n);i++)
{
    //If n/m - m/2 + 1/2 is integer: count++
}
count is the no. of ways.
  • Проголосовать: нравится
  • +29
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 2   Проголосовать: нравится -17 Проголосовать: не нравится

Why is the upperbound sqrt(2n) for m? Edit: My bad I apologize, got it