829. Consecutive Numbers Sum - Solution

The problem

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 <= 10⁹

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.

Python

def consecutive_numbers_sum(n):
    count = 0
    m = 1
    while m * (m - 1) // 2 < n:
        if (n - m * (m - 1) // 2) % m == 0:
            count += 1
        m += 1
    return count

Java

public class Solution {
    public int consecutiveNumbersSum(int n) {
        int count = 0;
        for (int m = 1; m * (m - 1) / 2 < n; ++m) {
            if ((n - m * (m - 1) / 2) % m == 0) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.consecutiveNumbersSum(15));
    }
}

C++

#include <iostream>

int consecutiveNumbersSum(int n) {
    int count = 0;
    for (int m = 1; m * (m - 1) / 2 < n; ++m) {
        if ((n - m * (m - 1) / 2) % m == 0)
            count++;
    }
    return count;
}

int main() {
    std::cout << consecutiveNumbersSum(15) << std::endl;
    return 0;
}

JavaScript

function consecutiveNumbersSum(n) {
    let count = 0;
    let m = 1;
    while (m * (m - 1) / 2 < n) {
        if ((n - m * (m - 1) / 2) % m === 0) {
            count++;
        }
        m++;
    }
    return count;
}

console.log(consecutiveNumbersSum(15));

using System;

public class Program {
    public static int ConsecutiveNumbersSum(int n) {
        int count = 0;
        for (int m = 1; m * (m - 1) / 2 < n; ++m) {
            if ((n - m * (m - 1) / 2) % m == 0) {
                count++;
            }
        }
        return count;
    }

    public static void Main() {
        Console.WriteLine(ConsecutiveNumbersSum(15));
    }
}

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.

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.

Python

def consecutive_numbers_sum(n):
    memo = {}

    def count_ways(k, remaining):
        if remaining == 0:
            return 1
        if remaining < 0 or k <= 0:
            return 0
        if (k, remaining) in memo:
            return memo[(k, remaining)]

        memo[(k, remaining)] = count_ways(k - 1, remaining) + count_ways(k - 1, remaining - k)
        return memo[(k, remaining)]

    return count_ways(n, n)

Java

import java.util.HashMap;
import java.util.Map;

public class Solution {
    private Map<String, Integer> memo = new HashMap<>();

    private int countWays(int k, int remaining) {
        if (remaining == 0) return 1;
        if (remaining < 0 || k <= 0) return 0;
        String key = k + "," + remaining;
        if (memo.containsKey(key)) return memo.get(key);

        int result = countWays(k - 1, remaining) + countWays(k - 1, remaining - k);
        memo.put(key, result);
        return result;
    }

    public int consecutiveNumbersSum(int n) {
        return countWays(n, n);
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.consecutiveNumbersSum(15));
    }
}

C++

#include <iostream>
#include <unordered_map>

std::unordered_map<int, int> memo;

int countWays(int k, int remaining) {
    if (remaining == 0) return 1;
    if (remaining < 0 || k <= 0) return 0;
    if (memo.find(k * 1000000 + remaining) != memo.end())
        return memo[k * 1000000 + remaining];

    memo[k * 1000000 + remaining] = countWays(k - 1, remaining) + countWays(k - 1, remaining - k);
    return memo[k * 1000000 + remaining];
}

int consecutiveNumbersSum(int n) {
    return countWays(n, n);
}

int main() {
    std::cout << consecutiveNumbersSum(15) << std::endl;
    return 0;
}

JavaScript

function consecutiveNumbersSum(n) {
    const memo = {};

    function countWays(k, remaining) {
        if (remaining === 0) return 1;
        if (remaining < 0 || k <= 0) return 0;
        const key = `${k},${remaining}`;
        if (key in memo) return memo[key];

        memo[key] = countWays(k - 1, remaining) + countWays(k - 1, remaining - k);
        return memo[key];
    }

    return countWays(n, n);
}

console.log(consecutiveNumbersSum(15));

using System;
using System.Collections.Generic;

public class Solution {
    private Dictionary<(int, int), int> memo = new Dictionary<(int, int), int>();

    private int CountWays(int k, int remaining) {
        if (remaining == 0) return 1;
        if (remaining < 0 || k <= 0) return 0;
        if (memo.ContainsKey((k, remaining))) return memo[(k, remaining)];

        int result = CountWays(k - 1, remaining) + CountWays(k - 1, remaining - k);
        memo[(k, remaining)] = result;
        return result;
    }

    public int ConsecutiveNumbersSum(int n) {
        return CountWays(n, n);
    }

    public static void Main() {
        Solution sol = new Solution();
        Console.WriteLine(sol.ConsecutiveNumbersSum(15));
    }
}

Defines a recursive function with memoization that attempts to form the number using remaining elements k. Helps to cut down on repeated calculations.

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:

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).

TypeScript

function consecutiveNumbersSum(n: number): number {
    let ans = 0;
    n <<= 1;
    for (let k = 1; k * (k + 1) <= n; ++k) {
        if (n % k === 0 && (Math.floor(n / k) + 1 - k) % 2 === 0) {
            ++ans;
        }
    }
    return ans;
}

func consecutiveNumbersSum(n int) int {
	n <<= 1
	ans := 0
	for k := 1; k*(k+1) <= n; k++ {
		if n%k == 0 && (n/k+1-k)%2 == 0 {
			ans++
		}
	}
	return ans
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
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	–

Complexity analysis

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.

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.

Consecutive Numbers Sum solution and explanation

The problem

Approach overview

Approach 1: Mathematical Approach

Approach 2: Recursive Approach with Memoization

Approach 3: Mathematical Derivation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Consecutive Numbers Sum solution and explanation

The problem

Approach overview

Approach 1: Mathematical Approach

Approach 2: Recursive Approach with Memoization

Approach 3: Mathematical Derivation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems