Problem

Given an integer n, return the number of ways you can write n as the sum of consecutive positive integers.

Examples

Example 1

1
2
3

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

Example 2

1
2
3

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

Example 3

1
2
3

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

Constraints

  • 1 <= n <= 109

Solution

Method 1 – Math (Enumerate Sequence Length)

Intuition

Any number n can be written as a sum of k consecutive positive integers if and only if there exist integers k ≥ 1 and a ≥ 1 such that:

n = a + (a+1) + (a+2) + ... + (a+k-1)

This sum equals:

n = k*a + k*(k-1)/2
=> a = (n - k*(k-1)/2) / k

We want a to be a positive integer, so for each k, if (n - k*(k-1)/2) is positive and divisible by k, we count it as a valid way.

Approach

  1. For k from 1 upwards, compute s = k*(k-1)/2.
  2. While s < n:
    • If (n - s) % k == 0, increment the answer.
    • Increment k.
  3. Stop when s >= n.

Code

1
2
3
4
5
6
7
8
9

class Solution:
    def consecutiveNumbersSum(self, n: int) -> int:
        ans = 0
        k = 1
        while k * (k - 1) // 2 < n:
            if (n - k * (k - 1) // 2) % k == 0:
                ans += 1
            k += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public int consecutiveNumbersSum(int n) {
        int ans = 0;
        for (int k = 1; k * (k - 1) / 2 < n; ++k) {
            if ((n - k * (k - 1) / 2) % k == 0) {
                ans++;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int consecutiveNumbersSum(int n) {
        int ans = 0;
        for (long k = 1; k * (k - 1) / 2 < n; ++k) {
            if ((n - k * (k - 1) / 2) % k == 0) {
                ++ans;
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9

func consecutiveNumbersSum(n int) int {
    ans := 0
    for k := 1; k*(k-1)/2 < n; k++ {
        if (n-k*(k-1)/2)%k == 0 {
            ans++
        }
    }
    return ans
}
1
2
3
4
5
6
7
8
9

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

Complexity

  • ⏰ Time complexity: O(√n), since k*(k-1)/2 < n ⇒ k = O(√n).
  • 🧺 Space complexity: O(1), only a few variables are used.