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) × k / 2, which simplifies to n × 2 = (a × 2 + k - 1) × k. From this, we can deduce that k must divide n × 2 evenly, and (n × 2) / k - k + 1 must be an even number.
Given that a ≥ 1, it follows that n × 2 = (a × 2 + k - 1) × k ≥ k × (k + 1).
In summary, we can conclude:
- k must divide n × 2 evenly;
- k × (k + 1) ≤ n × 2;
- (n × 2) / k - k + 1 must be an even number.
We start enumerating from k = 1, and we can stop when k × (k + 1) > n × 2. During the enumeration, we check if k divides n × 2 evenly, and if (n × 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(√n), where n is the given positive integer. The space complexity is O(1).
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(code-box)
