Given a number N, find the number of ways to write it as a sum of two or more consecutive integers
Posted
by
hilal
on Stack Overflow
See other posts from Stack Overflow
or by hilal
Published on 2010-12-27T06:05:16Z
Indexed on
2010/12/27
7:54 UTC
Read the original article
Hit count: 213
Here is the problem (Given a number N, find the number of ways to write it as a sum of two or more consecutive integers) and example 15 = 7+8, 1+2+3+4+5, 4+5+6
I solved with math like that :
a + (a + 1) + (a + 2) + (a + 3) + ... + (a + k) = N
(k + 1)*a + (1 + 2 + 3 + ... + k) = N
(k + 1)a + k(k+1)/2 = N
(k + 1)*(2*a + k)/2 = N
Then check that if N divisible by (k+1) and (2*a+k) then I can find answer in O(N) time
Here is my question how can you solve this by dynamic-programming ? and what is the complexity (O) ?
P.S : excuse me, if it is a duplicate question. I searched but I can find
© Stack Overflow or respective owner
