Problem statement

Given a positive integer n, return the number of ways to write n as the sum of one or more consecutive positive integers.

A single number counts as a run of length one, so the answer is always at least 1.

Example 1

Input: n = 5
Output: 2
Explanation: 5 = 5 = 2 + 3.

Example 2

Input: n = 9
Output: 3
Explanation: 9 = 9 = 4 + 5 = 2 + 3 + 4.

Example 3

Input: n = 15
Output: 4
Explanation: 15 = 15 = 7 + 8 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5.

Constraints

• 1 <= n <= 10^9

Hints for Consecutive Numbers Sum

1. Hint 1

   A run of k numbers starting at a sums to k*a + k(k-1)/2. For a fixed length k, is there at most one valid start?

2. Hint 2

   So you could count the lengths k (up to about sqrt(2n)) for which n - k(k-1)/2 is a positive multiple of k.

3. Hint 3

   Even faster: 2n = k * (2a + k - 1), and the two factors have opposite parity. Each odd divisor of n gives exactly one such split — count the odd divisors.

How to solve Consecutive Numbers Sum

The number of ways equals the number of odd divisors of n, which a trial-division factorisation counts in O(√n).

Approach

1. Divide out every factor 2 from n — powers of two do not change the count.
2. Factor the remaining odd number by trial division over odd d while d*d <= n, recording each exponent e.
3. The number of odd divisors is the product of e + 1 over the odd prime factors; a leftover factor above 1 is a prime with exponent 1 (multiply by 2).
4. Return that product.

Why it works

A run of k terms starting at a >= 1 satisfies 2n = k(2a + k - 1). The factors k and 2a + k - 1 have opposite parity (their difference 2a - 1 is odd) and the second is the larger. Conversely every factorisation 2n = u*v with u < v of opposite parity gives a run with k = u and a = (v - u + 1)/2 >= 1. In such a pair exactly one factor is odd, and it is an odd divisor d of n (all the 2s sit in the other factor); each odd divisor determines its pair. So runs and odd divisors are in one-to-one correspondence.

Complexity

• Time — O(√n)
• Space — O(1)

Pitfalls

• Counting all divisors instead of odd ones: 4 has three divisors but only one way (4 itself).
• If you loop over lengths k, compute k*(k+1)/2 in 64-bit or compare carefully — near 10^9 it is close to the int32 limit.
• Trying every start a is O(n) per start and far too slow for 10^9.

Reference solution

Python

def consecutiveNumbersSum(n: int) -> int:
    while n % 2 == 0:
        n //= 2
    count = 1
    d = 3
    while d * d <= n:
        e = 0
        while n % d == 0:
            n //= d
            e += 1
        count *= e + 1
        d += 2
    if n > 1:
        count *= 2
    return count

Java

public static int consecutiveNumbersSum(int n) {
    while (n % 2 == 0) n /= 2;
    int count = 1;
    for (long d = 3; d * d <= n; d += 2) {
        int e = 0;
        while (n % d == 0) {
            n /= d;
            e++;
        }
        count *= e + 1;
    }
    if (n > 1) count *= 2;
    return count;
}

C++

int consecutiveNumbersSum(int n) {
    while (n % 2 == 0) n /= 2;
    int count = 1;
    for (long long d = 3; d * d <= n; d += 2) {
        int e = 0;
        while (n % d == 0) {
            n /= d;
            e++;
        }
        count *= e + 1;
    }
    if (n > 1) count *= 2;
    return count;
}

JavaScript

var consecutiveNumbersSum = function(n) {
    while (n % 2 === 0) n /= 2;
    var count = 1;
    for (var d = 3; d * d <= n; d += 2) {
        var e = 0;
        while (n % d === 0) {
            n /= d;
            e++;
        }
        count *= e + 1;
    }
    if (n > 1) count *= 2;
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Subtraction in Linked List Hard
• GCD Sort of an Array Hard
• Count Valid Paths in a Tree Hard
• Create Components With Same Value Hard
• Cat and Mouse Hard
• Find the Number of Subsequences With Equal GCD Hard