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:
- $k$ must divide $n \times 2$ evenly;
- $k \times (k + 1) \leq n \times 2$;
- $(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 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 |
|