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 <= 109In #829 Consecutive Numbers Sum, the goal is to count how many ways a positive integer n can be written as a sum of consecutive positive integers. Instead of trying every possible sequence, the key observation is that any sequence of length k starting from x can be expressed mathematically as n = x + (x+1) + ... + (x+k-1). This arithmetic series can be simplified to a formula involving k and the starting value.
By rearranging the equation, the problem becomes checking whether a valid integer starting value exists for different sequence lengths. This converts the problem into a mathematical enumeration task rather than brute-force simulation. You only need to iterate over feasible sequence lengths and verify whether the derived starting number is a positive integer.
Because the sequence length cannot grow arbitrarily large, the search space is bounded by a value proportional to √n. This makes the approach efficient even for large inputs while using constant additional memory.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Mathematical enumeration of sequence lengths | O(√n) | O(1) |
NeetCode
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this problem appear in technical interviews because it tests mathematical insight and the ability to optimize brute-force ideas. Interviewers often look for candidates who recognize the arithmetic progression relationship and reduce the problem to √n checks.
A direct brute-force approach would try many starting points and sequences, which becomes inefficient for large numbers. Using the arithmetic series formula converts the problem into checking divisibility conditions, allowing us to evaluate only feasible sequence lengths.
The optimal approach uses mathematical transformation of the consecutive sum formula. By expressing the sum as an arithmetic series and iterating over possible sequence lengths, you can check whether a valid starting integer exists. This reduces the search space to about √n possibilities.
No complex data structure is required. The solution relies mainly on mathematical reasoning and simple iteration, using only a few integer variables to test valid sequence lengths.