Given a number N, find the number of ways to write it as a sum of two or more consecutive integers
Given a number N, find the number of ways to write it as a sum of two or more consecutive integers Here is the problem that tagged as dynamic-programming (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(sqrt(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 Is there any reason specifically to believe that dynamic programming would be appropriate here? I know of a different solution to this problem that naturally lends itself to DP, but this solution doesn't exhibit the optimal subst...