Leetcode 829.连续整数求和

Posted on |

829.连续整数求和

题目

给定一个正整数 N，试求有多少组连续正整数满足所有数字之和为 N?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
示例 1:

输入: 5
输出: 2
解释: 5 = 5 = 2 + 3，共有两组连续整数([5],[2,3])求和后为 5。
示例 2:

输入: 9
输出: 3
解释: 9 = 9 = 4 + 5 = 2 + 3 + 4
示例 3:

输入: 15
输出: 4
解释: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5
说明: 1 <= N <= 10 ^ 9

方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def consecutiveNumbersSum(self, N):
        """
        :type N: int
        :rtype: int
        """
        while N&1==0:
            N = N>>1
        ans = 1
        d =3
        while d*d<=N:
            e = 0
            while N%d==0:
                e += 1
                N = N/d
            ans *= e+1
            d += 2
        if N>1: ans*=2
        return ans
1
2
3
4
5
6
7
8
class Solution(object):
    def consecutiveNumbersSum(self, N):
        """
        :type N: int
        :rtype: int
        """
        N2 = 2 * N
        return sum(1 for i in range(1,int(math.sqrt(N2) + 1)) if N2 % i == 0 and (N2/float(i) - i + 1) % 2 == 0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def consecutiveNumbersSum(self, N):
        """
        :type N: int
        :rtype: int
        """
        i, ans = 1, 0
        N *= 2
        while i * i <= N:
            if N % i == 0:
                if (i + N // i - 1) & 1 == 0:
                    j = (i + N // i - 1) // 2
                    if i > j:
                        ans += 1
                    if N // i > j:
                        ans += 1
            i += 1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def consecutiveNumbersSum(self, N):
        """
        :type N: int
        :rtype: int
        """
        r = 1

        i=1
        k=i
        while k<N:
            i += 1
            if (N-k)%i == 0:
                if (N-k)//i > 0:
                    r += 1
                else:
                    break
            k+=i
        return r
1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def consecutiveNumbersSum(self, N):
        r = 1
        i = 1
        while True:
            N -= i
            i += 1
            if N<i: break
            if N%i == 0: r += 1
        return r