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

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}

Rearrange:

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

So:

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

For a valid representation:

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}

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:

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

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: