Consecutive Numbers Sum - Video Solutions

Problem Overview: Given an integer n, count how many ways it can be written as a sum of consecutive positive integers. For example, 15 = 1+2+3+4+5 = 4+5+6 = 7+8 = 15, so the answer is 4.

Approach 1: Mathematical Enumeration (O(sqrt(n)) time, O(1) space)

Any sequence of k consecutive numbers starting from x has sum x + (x+1) + ... + (x+k-1). Using the arithmetic series formula, the sum becomes k*x + k*(k-1)/2 = n. Rearranging gives x = (n - k*(k-1)/2) / k. For a valid sequence, x must be a positive integer. Iterate over possible lengths k while k*(k-1)/2 < n and check if the numerator is divisible by k. This converts the problem into simple number enumeration using properties of arithmetic progressions. The loop runs up to roughly sqrt(2n), making it very efficient.

This approach relies heavily on number theory and works without constructing the sequences themselves. It is a common pattern in math and enumeration problems where algebraic manipulation reduces the search space dramatically.

Approach 2: Recursive Approach with Memoization (O(n * sqrt(n)) time, O(n) space)

Another way is to explicitly build sequences. Start from each possible number and recursively add the next consecutive value while tracking the running sum. If the sum reaches n, count one valid representation. If the sum exceeds n, stop exploring that branch. Memoization stores intermediate states like (current_start, current_sum) so repeated subproblems are not recomputed.

This recursive search effectively enumerates all possible consecutive sequences. Memoization avoids recomputing identical states, but the state space still grows with n. As a result, the time complexity is significantly higher than the mathematical solution. The method is useful when practicing recursion and dynamic programming concepts, but it is not the most efficient choice for large inputs.

Recommended for interviews: The mathematical enumeration approach is what interviewers usually expect. It shows you can transform a brute-force search into a formula-based check and reduce complexity to O(sqrt(n)). Implementing the recursive enumeration first can demonstrate problem understanding, but the optimized math solution demonstrates stronger algorithmic insight.