Skip to content

829. Consecutive Numbers Sum

Description

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

Solutions

Solution 1: 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)\).

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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;
}

Comments