Leetcode 829 Consecutive Numbers Sum

发表于 |

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 = 7+8 = 4+5+6 = 1+2+3+4+5

Note: 1<=N<=10^9

思路：
这道题就是问一个数写成若干个连续正整数的和共有多少种形式？那么就非常简单了
如果能写成1个连续的整数，那么这个数能表示成a
如果能写成2个连续的整数，那么这个数能表示成a+(a+1)=2a+1
如果能写成3个连续的整数，那么这个数能表示成a+(a+1)+(a+2)=3a+3
如果能写成n个连续的整数，那么这个数能表示成na+n(n-1)/2

1
2
3
4
5
6
7
8
9
10
11
12
13
def consecutiveNumbersSum(N):
    res = 1
    n = 2
    while 1:
        divisor = N - (n-1)*n/2
        # 因为a至少为1，所以一旦小于就可以直接返回结果
        if divisor < n: return res
        res += divisor%n==0
        n += 1

"difficulty: medium
170 / 170 test cases passed.
Runtime: 238 ms"