# Consecutive Numbers Sum
**Difficulty:** HARD
[External](https://leetcode.com/problems/consecutive-numbers-sum)
Canonical: https://scaleengineer.com/dsa/problems/consecutive-numbers-sum
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
---
## Problem
Given an integer `n`, return _the number of ways you can write_ `n` _as the sum of consecutive positive integers._

**Example 1:**

**Input:** n = 5
**Output:** 2
**Explanation:** 5 = 2 + 3

**Example 2:**

**Input:** n = 9
**Output:** 3
**Explanation:** 9 = 4 + 5 = 2 + 3 + 4

**Example 3:**

**Input:** n = 15
**Output:** 4
**Explanation:** 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5

**Constraints:**

* `1 <= n <= 109`

# Approaches
## Brute-force with Nested Loops
This approach directly simulates the process described in the problem. We try every possible starting positive integer and, for each, we build a sum of consecutive integers. If the sum equals `n`, we count it as one way.
**Time:** O(n^2) - In the worst case, the outer loop runs `n` times, and the inner loop can also run up to `n` times, leading to a quadratic time complexity. This is too slow for `n` up to 10^9. · **Space:** O(1) - We only use a few variables to store the count and the current sum.
**Pros:** Simple to understand and implement.
**Cons:** Extremely inefficient and will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
We can use two nested loops. The outer loop iterates through all possible starting numbers `start` from 1 up to `n`. The inner loop adds consecutive numbers to `start`, forming a `currentSum`.
- If `currentSum` equals `n`, we've found a valid sequence, so we increment our counter and break the inner loop to try the next `start`.
- If `currentSum` exceeds `n`, the current sequence is too large, so we break the inner loop and move to the next `start`.
This method is very intuitive but its inefficiency makes it impractical for large values of `n`.

```java
class Solution {
    public int consecutiveNumbersSum(int n) {
        int count = 0;
        for (int start = 1; start <= n; start++) {
            long currentSum = 0;
            for (int j = start; j <= n; j++) {
                currentSum += j;
                if (currentSum == n) {
                    count++;
                    break;
                }
                if (currentSum > n) {
                    break;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize `count = 0`.
- Iterate with an outer loop for `start` from 1 to `n`.
- Inside the outer loop, initialize `currentSum = 0`.
- Start an inner loop for `j` from `start` to `n`.
- Add `j` to `currentSum`.
- If `currentSum == n`, increment `count` and break the inner loop.
- If `currentSum > n`, break the inner loop.
- Return `count`.

## Optimized Approach by Iterating on Sequence Length
A more efficient approach is to rephrase the problem mathematically. If `n` is a sum of `k` consecutive positive integers starting from `x`, we have the equation: `n = x + (x+1) + ... + (x+k-1)`. This simplifies to `n = k*x + k*(k-1)/2`. We can iterate through possible lengths `k` and check if a valid positive integer `x` exists.
**Time:** O(sqrt(n)) - The loop for `k` runs as long as `k^2` is approximately less than or equal to `2n`. Thus, `k` goes up to `sqrt(2n)`, making the complexity O(sqrt(n)). This is efficient enough for the given constraints. · **Space:** O(1) - We only use a few variables for the loop and calculation.
**Pros:** Much more efficient than the brute-force approach.; Passes the time limits for the given constraints.
**Cons:** Can be slightly less performant than the number theory approach for certain inputs (e.g., when n has many factors of 2).
### Explanation
From the equation `n = k*x + k*(k-1)/2`, we can solve for `x`: `x = (n - k*(k-1)/2) / k`.
For a given length `k`, a valid solution exists if:
1. `x` is an integer. This means `(n - k*(k-1)/2)` must be divisible by `k`.
2. `x` is positive. This means `n - k*(k-1)/2 > 0`, which implies `n > k*(k-1)/2`. This also gives us an upper bound for `k`. Since `k*(k-1)/2` is roughly `k^2/2`, `k` can go up to approximately `sqrt(2n)`.

The algorithm iterates `k` from 1 upwards as long as `k*(k+1)/2 <= n`. For each `k`, it checks if `(n - k*(k-1)/2)` is divisible by `k`. If it is, we've found a valid way.

```java
class Solution {
    public int consecutiveNumbersSum(int n) {
        int count = 0;
        // k is the number of terms in the series
        for (long k = 1; k * (k + 1) / 2 <= n; k++) {
            // From n = x*k + k*(k-1)/2, we get x*k = n - k*(k-1)/2.
            // We need to check if (n - k*(k-1)/2) is a positive multiple of k.
            // The loop condition k*(k+1)/2 <= n ensures x >= 1.
            if ((n - k * (k - 1) / 2) % k == 0) {
                count++;
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize `count = 0`.
- Loop for `k` (the length of the sequence) starting from 1.
- The loop condition can be `k * (k + 1) / 2 <= n`, as this ensures the starting number `x` can be at least 1.
- Inside the loop, calculate the sum of the arithmetic series part: `seriesSum = k * (k - 1) / 2`.
- Calculate the remaining part that would be `k*x`: `remainder = n - seriesSum`.
- If `remainder > 0` and `remainder % k == 0`, it means a valid positive integer `x` exists. Increment `count`.
- After the loop finishes, return `count`.

## Mathematical Approach using Odd Divisors
This is the most optimal approach, based on a number theory insight. The problem of finding the number of ways to write `n` as a sum of consecutive integers is equivalent to finding the number of odd divisors of `n`.
**Time:** O(sqrt(n)) - In the worst case, `n` is a large prime or a product of large primes. The main work is the loop for prime factorization which runs up to `sqrt(m)`, where `m` is the odd part of `n`. Since `m <= n`, the complexity is bounded by O(sqrt(n)). · **Space:** O(1) - Constant extra space is used.
**Pros:** The most efficient method.; Mathematically elegant.; Performs significantly better than the other O(sqrt(n)) approach when `n` has many factors of 2.
**Cons:** The underlying mathematical reasoning is less intuitive than the other approaches.
### Explanation
Starting from the equation `n = k*x + k*(k-1)/2`, we can rearrange it to `2n = k(2x + k - 1)`.
Let `A = k` and `B = 2x + k - 1`. We are looking for pairs of factors `(A, B)` of `2n`.
Notice that `B - A = (2x + k - 1) - k = 2x - 1`, which is always an odd number. This implies that one of `A` and `B` must be odd, and the other must be even.

Let the prime factorization of `n` be `n = 2^p * m`, where `m` is an odd number. Then `2n = 2^(p+1) * m`.
Any factor of `2n` is a product of a power of 2 (from `2^(p+1)`) and a factor of `m`. For `A` and `B` to have different parity, one must contain all the factors of 2, i.e., `2^(p+1)`, and the other must be purely odd.

This means that for every odd divisor `d` of `n`, we can form a pair of factors of `2n` with different parity. This pair corresponds to a unique valid solution for `x` and `k`. Therefore, the number of ways is simply the number of odd divisors of `n`, which is the same as the number of divisors of its largest odd part, `m`.

The algorithm is to first find `m` by dividing `n` by 2 until it's odd, and then count the divisors of `m`.

```java
class Solution {
    public int consecutiveNumbersSum(int n) {
        // The problem is equivalent to finding the number of odd divisors of n.
        
        // Step 1: Remove all factors of 2 from n to get its largest odd part.
        while ((n & 1) == 0) { // while n is even
            n >>= 1; // n = n / 2
        }
        
        int result = 1;
        // Step 2: Find the number of divisors of the remaining odd number n.
        // We do this by finding its prime factorization: n = p1^a1 * p2^a2 * ...
        // The number of divisors is (a1+1)*(a2+1)*...
        for (int i = 3; i * i <= n; i += 2) {
            int count = 0;
            while (n % i == 0) {
                n /= i;
                count++;
            }
            result *= (count + 1);
        }
        
        // If n is still greater than 1, it means the remaining n is a prime factor.
        if (n > 1) {
            result *= 2;
        }
        
        return result;
    }
}
```
### Algorithm
- First, find the largest odd divisor of `n`. Keep dividing `n` by 2 until it becomes odd.
- Let the resulting odd number be `m`.
- Now, find the number of divisors of `m`. Initialize `result = 1`.
- Iterate through odd numbers `d` from 3 up to `sqrt(m)`.
- If `d` divides `m`:
    - Count how many times `d` is a factor of `m`. Let this be `exponent`.
    - Update `m` by dividing it by `d` repeatedly: `m = m / d`.
    - Update the result: `result = result * (exponent + 1)`.
- After the loop, if `m > 1`, it means the remaining `m` is a prime factor. Multiply `result` by 2.
- Return `result`.

# Solutions
### Java

```java
class Solution {
public
  int consecutiveNumbersSum(int n) {
    n <<= 1;
    int ans = 0;
    for (int k = 1; k * (k + 1) <= n; ++k) {
      if (n % k == 0 && (n / k + 1 - k) % 2 == 0) {
        ++ans;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int consecutiveNumbersSum(int n) {
    n <<= 1;
    int ans = 0;
    for (int k = 1; k * (k + 1) <= n; ++k) {
      if (n % k == 0 && (n / k + 1 - k) % 2 == 0) {
        ++ans;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def consecutiveNumbersSum(self, n: int) -> int: n <<= 1 ans, k = 0, 1 while k * (k + 1) <= n: if n % k == 0 and (n // k + 1 - k) % 2 == 0: ans += 1 k += 1 return ans

```