# LeetCode 829: Consecutive Numbers Sum

## Problem Restatement

We are given a positive integer `n`.

We need to count how many different ways `n` can be written as the sum of consecutive positive integers.

For example:

```python
15 = 15
15 = 7 + 8
15 = 4 + 5 + 6
15 = 1 + 2 + 3 + 4 + 5
```

So the answer for `15` is:

```python
4
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | A positive integer `n` |
| Output | Number of valid consecutive-integer representations |
| Consecutive | Numbers differ by exactly `1` |
| Positive integers | All numbers must be greater than `0` |

Function shape:

```python
class Solution:
    def consecutiveNumbersSum(self, n: int) -> int:
        ...
```

## Examples

Example 1:

```python
n = 5
```

Possible representations:

```python
5
2 + 3
```

So the answer is:

```python
2
```

Example 2:

```python
n = 9
```

Possible representations:

```python
9
4 + 5
2 + 3 + 4
```

So the answer is:

```python
3
```

Example 3:

```python
n = 15
```

Possible representations:

```python
15
7 + 8
4 + 5 + 6
1 + 2 + 3 + 4 + 5
```

So the answer is:

```python
4
```

## First Thought: Brute Force

We can try every possible starting number.

For each start, keep adding consecutive integers until the sum reaches or exceeds `n`.

```python
class Solution:
    def consecutiveNumbersSum(self, n: int) -> int:
        count = 0

        for start in range(1, n + 1):
            total = 0
            current = start

            while total < n:
                total += current
                current += 1

            if total == n:
                count += 1

        return count
```

This works, but it is inefficient.

## Problem With Brute Force

The outer loop can run up to `n` times.

The inner loop may also run many times.

The total runtime can approach:

```python
O(n^2)
```

This is too slow for large values of `n`.

We need a mathematical observation.

## Key Insight

Suppose:

```python
n = x + (x + 1) + (x + 2) + ... + (x + k - 1)
```

This is a sequence of:

```python
k
```

consecutive numbers starting from:

```python
x
```

Using the arithmetic series formula:

```python
n = kx + \frac{k(k - 1)}{2}
```

$$
n = kx + \frac{k(k-1)}{2}
$$

Rearrange:

```python
kx = n - \frac{k(k - 1)}{2}
```

So:

```python
x = \frac{n - \frac{k(k - 1)}{2}}{k}
```

For a valid representation:

| Requirement | Reason |
|---|---|
| `x` must be an integer | Starting number must be whole |
| `x > 0` | Numbers must be positive |

So for every possible length `k`, we only need to check whether:

```python
n - \frac{k(k - 1)}{2}
```

is divisible by `k`.

## Important Observation

The smallest sum of `k` consecutive positive integers is:

```python
1 + 2 + ... + k
```

which equals:

```python
\frac{k(k+1)}{2}
```

$$
\frac{k(k+1)}{2}
$$

So once:

```python
\frac{k(k+1)}{2} > n
```

no larger `k` can work.

That gives an `O(sqrt(n))` solution.

## Algorithm

Try every possible sequence length `k`.

For each `k`:

1. Compute:

```python
remainder = n - k * (k - 1) // 2
```

2. If:

```python
remainder % k == 0
```

then a valid starting value exists.

3. Increase the answer count.

Stop when:

```python
k * (k + 1) // 2 > n
```

## Walkthrough

Use:

```python
n = 15
```

Try:

```python
k = 1
```

Then:

```python
remainder = 15
15 % 1 == 0
```

Valid:

```python
15
```

Try:

```python
k = 2
```

Then:

```python
remainder = 15 - 1 = 14
14 % 2 == 0
```

Starting number:

```python
14 // 2 = 7
```

Valid sequence:

```python
7 + 8
```

Try:

```python
k = 3
```

Then:

```python
remainder = 15 - 3 = 12
12 % 3 == 0
```

Starting number:

```python
4
```

Valid sequence:

```python
4 + 5 + 6
```

Try:

```python
k = 4
```

Then:

```python
remainder = 15 - 6 = 9
9 % 4 != 0
```

Not valid.

Try:

```python
k = 5
```

Then:

```python
remainder = 15 - 10 = 5
5 % 5 == 0
```

Starting number:

```python
1
```

Valid sequence:

```python
1 + 2 + 3 + 4 + 5
```

Total valid sequences:

```python
4
```

## Correctness

Suppose a valid representation uses `k` consecutive positive integers starting at `x`.

Then:

```python
n = x + (x + 1) + ... + (x + k - 1)
```

Using the arithmetic series formula:

```python
n = kx + \frac{k(k - 1)}{2}
```

Rearranging:

```python
x = \frac{n - \frac{k(k - 1)}{2}}{k}
```

So for a fixed `k`, a valid sequence exists exactly when:

```python
n - \frac{k(k - 1)}{2}
```

is divisible by `k`, because then `x` is an integer.

The algorithm checks every possible sequence length `k` for which the smallest possible sum of `k` positive consecutive integers does not exceed `n`.

Therefore:

| Case | Result |
|---|---|
| Divisible remainder | Exactly one valid sequence |
| Non-divisible remainder | No valid sequence |

Since every valid sequence has exactly one length `k`, and every possible valid length is checked once, the algorithm counts every valid representation exactly once.

Therefore, the returned answer is correct.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(sqrt(n))` | Maximum valid `k` grows roughly as `sqrt(n)` |
| Space | `O(1)` | Only constant extra memory is used |

## Implementation

```python
class Solution:
    def consecutiveNumbersSum(self, n: int) -> int:
        count = 0
        k = 1

        while k * (k + 1) // 2 <= n:
            remainder = n - k * (k - 1) // 2

            if remainder % k == 0:
                count += 1

            k += 1

        return count
```

## Code Explanation

We try every possible sequence length:

```python
k = 1
```

The loop condition:

```python
k * (k + 1) // 2 <= n
```

checks whether even the smallest possible sequence of length `k` can fit inside `n`.

For each `k`, we compute:

```python
remainder = n - k * (k - 1) // 2
```

This corresponds to:

```python
kx
```

If:

```python
remainder % k == 0
```

then:

```python
x
```

is an integer, so a valid sequence exists.

We count it:

```python
count += 1
```

Finally:

```python
return count
```

returns the total number of valid representations.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.consecutiveNumbersSum(1) == 1
    assert s.consecutiveNumbersSum(5) == 2
    assert s.consecutiveNumbersSum(9) == 3
    assert s.consecutiveNumbersSum(15) == 4
    assert s.consecutiveNumbersSum(16) == 1
    assert s.consecutiveNumbersSum(45) == 6

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `1` | Smallest valid input |
| `5` | Two representations |
| `9` | Odd number with multiple forms |
| `15` | Standard example |
| `16` | Power of two has only one representation |
| `45` | Larger number with many valid decompositions |