Count k for consecutive-sum generator

An array generator service produces a consecutive-integers array starting at a positive integer k: [k, k+1, ..., k+m−1] for some m ≥ 1. The service returns such an array if its sum equals a given positive integer s. Given s, determine how many distinct k values admit at least one valid array. Provide an algorithm, prove correctness, and analyze time and space complexity. For example, when s = 10, valid k are 1 and 10.

Count k for consecutive-sum generator

An array generator service produces a consecutive-integers array starting at a positive integer k: [k, k+1, ..., k+m-1] for some m >= 1. The service returns such an array only if its sum equals a given positive integer s.

Given s, determine how many distinct positive integer values of k admit at least one valid array (i.e., for how many k does there exist some length m >= 1 with k + (k+1) + ... + (k+m-1) = s).

Example: for s = 10, the valid k are 1 (from [1,2,3,4]) and 10 (from [10]), so the answer is 2.

Write a function countK(s) that returns this count.

Constraints

• 1 <= s <= 10^9
• k is a positive integer (k >= 1)
• m, the array length, is >= 1

Hints

1. The sum of [k, k+1, ..., k+m-1] equals mk + m(m-1)/2. Set this equal to s.
2. For each candidate length m, k = (s - m*(m-1)/2) / m. A valid k exists iff the numerator is positive and divisible by m. Distinct m give distinct k, so just count the valid m.
3. Stop iterating m once m*(m-1)/2 >= s, which gives an O(sqrt(s)) loop.