Skip to main content
Talentd

Consecutive Numbers Sum - Solution & Explanation

HardMathEnumeration17 min readAsked at: Microsoft, Oracle, Airbnb +4
Practice this problem

Problem Statement

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 <= 109

Approach Overview

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.

Approach 1: Mathematical Approach

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.

Code

PythonC++JavaC#JavaScript

Python

C++

Java

C#

JavaScript

Complexity

Time Complexity: O(sqrt(2n))
Space Complexity: O(1)

Try this approach in the editor →

Approach 2: Recursive Approach with Memoization

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.

Code

PythonC++JavaC#JavaScript

Python

C++

Java

C#

JavaScript

Complexity

Time Complexity: O(kn) where k is the depth of recursion
Space Complexity: O(kn) for memoization table

Try this approach in the editor →

Approach 3: Mathematical Derivation

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:

  1. k must divide n times 2 evenly;
  2. k times (k + 1) leq n times 2;
  3. (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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Mathematical Approach

Time Complexity: O(sqrt(2n))
Space Complexity: O(1)

Recursive Approach with Memoization

Time Complexity: O(kn) where k is the depth of recursion
Space Complexity: O(kn) for memoization table

Mathematical Derivation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Mathematical EnumerationO(sqrt(n))O(1)Best general solution. Uses arithmetic series formula to check valid sequence lengths efficiently.
Recursive with MemoizationO(n * sqrt(n))O(n)Useful for understanding recursive enumeration of consecutive sequences and practicing memoization.

Video Solution

Leetcode 83 Problem 3 - Consecutive Numbers Sum (829) • code_report • 22,011 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Consecutive Numbers Sum easy or hard?
The problem is labeled Hard because the key insight is mathematical rather than algorithmic. Without recognizing the arithmetic series formula, most solutions attempt brute-force enumeration. Once the formula is derived, the implementation becomes short and efficient.
Consecutive Numbers Sum Python/Java solution
In Python or Java, implement a loop over sequence length k and compute (n - k*(k-1)/2). If the result is positive and divisible by k, increment the answer. This implementation runs in O(sqrt(n)) time and works efficiently even for large inputs.
How to solve Consecutive Numbers Sum in O(n)?
A straightforward enumeration can iterate starting numbers and keep adding consecutive integers until the sum reaches or exceeds n. This brute-force idea runs in roughly O(n) or worse depending on the implementation. Optimizing with the arithmetic series formula reduces the complexity further to O(sqrt(n)).
What is the best approach for Consecutive Numbers Sum?
The optimal approach uses a mathematical observation about arithmetic sequences. A sequence of length k starting at x sums to k*x + k*(k-1)/2. By iterating possible lengths k and checking if (n - k*(k-1)/2) is divisible by k, you can determine valid sequences in O(sqrt(n)) time with O(1) space.
Is Consecutive Numbers Sum asked at Google/Amazon/Meta?
Consecutive Numbers Sum is a classic number theory and enumeration problem similar to questions asked in Google and Amazon interviews. It tests whether you can translate a sequence problem into a mathematical formula and reduce brute-force search using algebra.
What data structure is used in Consecutive Numbers Sum?
The optimal solution does not require complex data structures. It relies on arithmetic formulas and integer checks. Alternative recursive implementations may use memoization with a hash map or dictionary to cache intermediate states.
What is the time complexity of Consecutive Numbers Sum?
The optimal mathematical solution runs in O(sqrt(n)) time because the sequence length k only needs to be tested up to roughly sqrt(2n). Space complexity is O(1) since the algorithm only keeps a few variables while checking divisibility conditions.

Ready to solve this problem?

Practice Consecutive Numbers Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer