Skip to content

Latest commit

 

History

History
151 lines (102 loc) · 3.22 KB

0829._Consecutive_Numbers_Sum.md

File metadata and controls

151 lines (102 loc) · 3.22 KB

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

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

反正就是等差数列，直接搞起呗

  • 这道题的要求的另一种说法: 把N表示成一个等差数列（公差为1）的和
  • 我们不妨设这个数列的首项是x，项数为m，则这个数列的和就是[x + (x + (m-1))]m / 2 = mx + m(m-1)/2 = N
  • 接下来，一个很自然的想法就是，枚举m，通过上式判断对于相应的m是否存在合法的x。
  • x = ((N - m(m-1)/2)) / m
  • 显然枚举的复杂度是O(sqrt(N))。因为m能取到的最大值显然是sqrt(n)数量级的

参考实在看不下去了其他啰嗦的解法,就是等差数列好吗

最推荐这种解法, beats 23.18%

class Solution:
    def consecutiveNumbersSum(self, N):
        """
        :type N: int
        :rtype: int
        """
        res = 0
        m = 1
        while 1:
            mx = N - m * (m-1) / 2
            if mx <= 0:
                break
            if mx % m == 0:
                res += 1
            m += 1
        return res

思路 3 - 时间复杂度: O(lgN)- 空间复杂度: O(1)******

另外一种数学上的解法[C++/Java/Python] 4-lines and O(logN), Count Odd Factors

这样可以更快, 特别是当N特别大的时候，beats 86.09%

class Solution:
    def consecutiveNumbersSum(self, N):
        """
        :type N: int
        :rtype: int
        """
        res = 1
        i = 3
        while N % 2 == 0:
            N /= 2
        while i * i <= N:
            count = 0
            while N % i == 0:
                N /= i
                count += 1
            res *= count + 1
            i += 2
        return res if N == 1 else res * 2