829. Consecutive Numbers Sum

829. Consecutive Numbers Sum

难度: Hard

刷题内容

原题连接

内容描述

Given a positive integer N, how many ways can we write it as a sum of consecutive positive integers?

Example 1:

Input: 5
Output: 2
Explanation: 5 = 5 = 2 + 3
Example 2:

Input: 9
Output: 3
Explanation: 9 = 9 = 4 + 5 = 2 + 3 + 4
Example 3:

Input: 15
Output: 4
Explanation: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5
Note: 1 <= N <= 10 ^ 9.

解题方案

思路 1
- 时间复杂度: O(sqrt(N))- 空间复杂度: O(1)

假设 (x+1) + (x+2) + ... + (x+k) = N,其中 x >= 0, k >= 1 那么 2N = (2x+k+1) * k, 所以 2x = 2N/k-k-1, 由于 x >= 0, 所以 2N/k - k - 1 >= 0, 所以 2N/k - k > 1, 所以 2N/k - k > 0 所以 k*k < 2N, 所以 k <= (int) sqrt(N)

beats 68.21%

class Solution:
    def consecutiveNumbersSum(self, N):
        """
        :type N: int
        :rtype: int
        """
        res = 0
        for k in range(1, int(math.sqrt(2*N))+1):
            if 2 * N % k != 0:
                continue
            y = 2 * N // k - k - 1 # 2x = 2N/k-k-1, y = 2x, y >= 0
            if y % 2 == 0 and y >= 0:
                res += 1
        return res
top Created with Sketch.