1340. Sums of Consecutive Numbers
Count the ways to write n as a sum of one or more CONSECUTIVE positive
integers. A single number counts as such a sum of length one.
9 -> 3 9 4+5 2+3+4
15 -> 4 15 7+8 4+5+6 1+2+3+4+5
16 -> 1 16
Trying every start and length is O(n^2). Write the sum down instead. Starting
at s with k terms:
s + (s+1) + ... + (s+k-1) = k*s + k(k-1)/2
So n has a sum of length k exactly when n - k(k-1)/2 is positive and
divisible by k, and that division gives s.
Now k cannot be large: k(k-1)/2 must stay below n, so k is at most about
sqrt(2n), which is under 50000 even at n = 10^9. One loop over k counts
everything.
The answer has a closed form too, being the number of odd divisors of n, which
is why every power of two answers 1 and 16 is in the tests. Deriving it is a
good follow-up, but the loop above is what an interview wants first.
Constraints - `1 ≤ n ≤ 1000000000`
Input
One line containing the integer n.
Output
Print how many ways n can be written as a sum of one or more consecutive positive integers.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.