Given an integer n, return the number of ways you can write n as the sum of consecutive positive integers.
Example 1:
Input: n = 5 Output: 2 Explanation: 5 = 2 + 3
Example 2:
Input: n = 9 Output: 3 Explanation: 9 = 4 + 5 = 2 + 3 + 4
Example 3:
Input: n = 15 Output: 4 Explanation: 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5
Constraints:
1 <= n <= 109Problem 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.
To determine if a number can be expressed as a sum of consecutive positive integers, observe that for a sequence starting with k and having m terms, the sum can be represented as:
S = k + (k+1) + ... + (k + m - 1) = mk + m(m-1)/2
which needs to equal n. Hence,
mk + m(m-1)/2 = n
Re-arranging gives:
m(k + (m-1)/2) = n
Therefore, we find distinct m such that the expression gives an integer value for k.
The solution iterates through potential values of m. For each m, it checks if the adjustment to n is divisible by m. If so, it increments the count.
Python
C++
Java
C#
JavaScript
Time Complexity: O(sqrt(2n))
Space Complexity: O(1)
This approach utilizes recursion to try different starting points for the sequence and calculate if they can sum up to n using memoization to avoid redundant calculations.
Defines a recursive function with memoization that attempts to form the number using remaining elements k. Helps to cut down on repeated calculations.
Python
C++
Java
C#
JavaScript
Time Complexity: O(kn) where k is the depth of recursion
Space Complexity: O(kn) for memoization table
Consecutive positive integers form an arithmetic sequence with a common difference d = 1. Let's assume the first term of the sequence is a, and the number of terms is k. Then, n = (a + a + k - 1) times k / 2, which simplifies to n times 2 = (a times 2 + k - 1) times k. From this, we can deduce that k must divide n times 2 evenly, and (n times 2) / k - k + 1 must be an even number.
Given that a geq 1, it follows that n times 2 = (a times 2 + k - 1) times k geq k times (k + 1).
In summary, we can conclude:
k must divide n times 2 evenly;k times (k + 1) leq n times 2;(n times 2) / k - k + 1 must be an even number.We start enumerating from k = 1, and we can stop when k times (k + 1) > n times 2. During the enumeration, we check if k divides n times 2 evenly, and if (n times 2) / k - k + 1 is an even number. If both conditions are met, it satisfies the criteria, and we increment the answer by one.
After finishing the enumeration, we return the answer.
The time complexity is O(\sqrt{n}), where n is the given positive integer. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Mathematical Approach | Time Complexity: O(sqrt(2n)) |
| Recursive Approach with Memoization | Time Complexity: O(kn) where k is the depth of recursion |
| Mathematical Derivation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Mathematical Enumeration | O(sqrt(n)) | O(1) | Best general solution. Uses arithmetic series formula to check valid sequence lengths efficiently. |
| Recursive with Memoization | O(n * sqrt(n)) | O(n) | Useful for understanding recursive enumeration of consecutive sequences and practicing memoization. |
Leetcode 83 Problem 3 - Consecutive Numbers Sum (829) • code_report • 21,939 views views
Watch 9 more video solutions →Practice Consecutive Numbers Sum with our built-in code editor and test cases.
Practice on FleetCode