leetcode/solution/0800-0899/0829.Consecutive Numbers Sum

comments	difficulty	edit_url	tags
true	Hard	https://github.com/doocs/leetcode/edit/main/solution/0800-0899/0829.Consecutive%20Numbers%20Sum/README_EN.md	Math Enumeration

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

Python3

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

Java

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;
    }
}

C++

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;
    }
};

Go

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
}

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;
}