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:

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

So the answer for 15 is:

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:

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

Examples

Example 1:

n = 5

Possible representations:

5
2 + 3

So the answer is:

2

Example 2:

n = 9

Possible representations:

9
4 + 5
2 + 3 + 4

So the answer is:

3

Example 3:

n = 15

Possible representations:

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

So the answer is:

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.

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:

O(n^2)

This is too slow for large values of n.

We need a mathematical observation.

Key Insight

Suppose:

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

This is a sequence of:

k

consecutive numbers starting from:

x

Using the arithmetic series formula:

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

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

Rearrange:

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

So:

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:

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

is divisible by k.

Important Observation

The smallest sum of k consecutive positive integers is:

1 + 2 + ... + k

which equals:

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

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

So once:

\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:

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

2. If:

remainder % k == 0

then a valid starting value exists.

3. Increase the answer count.

Stop when:

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

Walkthrough

Use:

n = 15

Try:

k = 1

Then:

remainder = 15
15 % 1 == 0

Valid:

15

Try:

k = 2

Then:

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

Starting number:

14 // 2 = 7

Valid sequence:

7 + 8

Try:

k = 3

Then:

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

Starting number:

4

Valid sequence:

4 + 5 + 6

Try:

k = 4

Then:

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

Not valid.

Try:

k = 5

Then:

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

Starting number:

1

Valid sequence:

1 + 2 + 3 + 4 + 5

Total valid sequences:

4

Correctness

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

Then:

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

Using the arithmetic series formula:

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

Rearranging:

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

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

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

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:

k = 1

The loop condition:

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

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

For each k, we compute:

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

This corresponds to:

kx

If:

remainder % k == 0

then:

x

is an integer, so a valid sequence exists.

We count it:

count += 1

Finally:

return count

returns the total number of valid representations.

Testing

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