LeetCode 829 - Consecutive Numbers Sum

https://leetcode.com/problems/consecutive-numbers-sum/description/

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.

https://leetcode.com/problems/consecutive-numbers-sum/discuss/128959/5-line-O(N-0.5)-Java-code-Math-method

N can be expressed as k + 1, k + 2, ..., k + i, therefore

N = k * i + (i + 1) * i / 2 =>
N - (i + 1) * i / 2 = k * i

Since N can always be written as N, we can start from i = 2, ans = 1.

    public int consecutiveNumbersSum(int N) {
        int ans = 1;
        for (int i = 2; i * (i + 1) / 2 <= N; ++i) {
            if ((N - i * (i + 1) / 2) % i == 0) ++ans;
        }
        return ans;
    }

As in Approach #2, $2*N = k(2*x + k + 1)$ with $x \geq 0, k \geq 1$. Call $k$ the first factor, and $2*x + k + 1$the second factor. We are looking for ways to solve this equation without trying all $2*N$ possibilities.

Now notice that the parity of $k$ and $(2*x + k + 1)$ are different. That is, if $k$ is even then the other quantity is odd, and vice versa. Also, $2*x + k + 1 \geq k + 1 > k$, so the second factor must be bigger.

Now write $2N = 2^\alpha * M$ where $M$ is odd. If we factor $M = a * b$, then two candidate solutions are $k = a, 2x+k+1 = b * 2^\alpha$, or $k = a * 2^\alpha, 2x+k+1 = b$. However, only one of these solutions will have the second factor larger than the first. (Because $\alpha \geq 1$, we are guaranteed that one factor is strictly larger.)

Thus, the answer is the number of ways to factor the odd part of $N$.

• Time Complexity: $O(\sqrt(N))$.
• Space Complexity: $O(1)$.

    public int consecutiveNumbersSum(int N) {

        while ((N & 1) == 0) N >>= 1;

        int ans = 1, d = 3;

        while (d * d <= N) {

            int e = 0;

            while (N % d == 0) {

                N /= d;

                e++;

            }

            ans *= e + 1;

            d += 2;

        }

        if (N > 1) ans <<= 1;

        return ans;

    }

We can model the situation by the equation $N = (x+1) + (x+2) + \cdots + (x+k)$. Here, $x \geq 0, k \geq 1$. Using the identity $1 + 2 + \cdots + k = \frac{k(k+1)}{2}$, we can simplify this equation to $2*N = k(2*x + k + 1)$.

From here, clearly $1 \leq k \leq 2*N$. We can try every such $k$. We need $x = \frac{\frac{2*N}{k} - k - 1}{2}$ to be a non-negative integer for a solution to exist for the $k$ we are trying.

    public int consecutiveNumbersSum(int N) {

        // 2N = k(2x + k + 1)

        int ans = 0;

        for (int k = 1; k <= 2*N; ++k)

            if (2 * N % k == 0) {

                int y = 2 * N / k - k - 1;

                if (y % 2 == 0 && y >= 0)

                    ans++;

            }

        return ans;

    }

Time Complexity: $O(N^2)$.

    public int consecutiveNumbersSum(int N) {

        int ans = 0;

        for (int start = 1; start <= N; ++start) {

            int target = N, x = start;

            while (target > 0)

                target -= x++;

            if (target == 0) ans++;

        }

        return ans;

    }

public int consecutiveNumbersSum(int N) {

  if (N < 0)

    return 0;

  int total = 1;

  for (int len = 2; len <= Math.ceil(N / 2d) + 1; len++) {

    if (len % 2 == 1) {

      if (N % len == 0 && N / len - len / 2 > 0) {

        ++total;

      }

    } else {

      // len even

      if (N % len != 0) {

        int num = N / len;

        if (num - len / 2 + 1 <= 0) // BUG

          // continue; //proof

          break;

        long expectSum = (2 * num + 1) * len / 2;

        if (expectSum == N) {

          ++total;

        }

      }

    }

  }

  return total;

}