$ cat ./coding/829-consecutive-numbers-sum.md

────────────────────────────────────────────────────────────

829. Consecutive Numbers Sum

題目給定一個 n ，要求要找出總共存在著幾組連續整數，其總和為 n ，這一題是困難等級的題目，不過存在著一個簡單的解（非最優解）。

題目有給一個條件是「連續整數」。連續 k 個整數可以用 $x,x+1,x+2,\dots ,x+k-1$來表示。

總和可以用 $\begin{array}{l}kx+(0+1+2+\dots +(k-1))=kx+\\ frac(k-1)k2\end{array}$ 來表示，以下例子以當 n = 15 時求解。

| k | 總和 | x | 組合 | | :--- | :--- | :--- | :--- | | 1 | x | 15 | 15 | | 2 | 2x + 1 | 7 | 7, 8 | | 3 | 3x + 3 | 4 | 4, 5, 6 | | 4 | 4x + 6 | 2.25 |  | | 5 | 5x + 10 | 1 | 1, 2, 3, 4, 5 | | 6 | 6x + 15 | 0 |  | | 7 | 7x + 21 | -0.857142857 |  |

透過上面的表格，我們就可以知道，

1. 可以從 k = 1 開始去求解
2. 求解的過程中 x 要是整數才是正確的
3. 總和的常數項，是前一個 k 值不斷累積起來的結果
4. k 的結束條件是當 k >= n 時就要結束。

class Solution:
    def consecutiveNumbersSum(self, n: int) -> int:
        ans = 0
        constant = 0
        divisor = 1
        while constant < n:
            if ((n - constant) / divisor).is_integer():
                ans += 1 

            constant = constant + divisor
            divisor += 1

        return ans

理論上時間複雜度應該只會到 $O(n/2)$。

$ ls ./coding/ | grep -v 829-consecutive-numbers-sum