829.Consecutive-Numbers-Sum

829. Consecutive Numbers Sum

题目地址

https://leetcode.com/problems/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 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5
Note: 1 <= N <= 10 ^ 9.

代码

Approach #1 Mathematical

连续自然数的和其实就是一个公差为1的等差数列的和，设这个数列是x,x+1,x+2,...,x+n，那么这个数列的和是(n+1)x+n(n+1)/2，这个数列的长度是n+1，第一个数字是x，然后就可以从数字长度为1开始逐渐尝试，看N能否分解成为长度为n的等差数列的和，如果可以，那么一定可以求得整数解x使得x=(N-n*(n+1))/(n+1)

class Solution {
  public int consecutiveNumbersSum(int N) {
        int res = 0;
    int n = 0;
    while (true) {
      int top = N - (n * n + n) / 2;
      if (top <= 0)    break;
      if (top % (n + 1) == 0) {
        res++;
      }
      n++;
    }
    return res;
  }
}