Consecutive Numbers Sum: Mathematical Decomposition

Given a positive integer n, return the number of ways you can write it as a sum of consecutive positive integers.

This is LeetCode 829: Consecutive Numbers Sum, a hard problem that looks like it needs brute-force search but collapses into a tight math loop once you see the underlying formula. The key is recognizing that consecutive sums are arithmetic series, and checking whether a valid starting point exists for each possible sequence length.

The problem

You are given a positive integer n. Return the number of ways n can be expressed as the sum of consecutive positive integers. For example:

• n = 5 returns 2: you can write 5 as 5 or as 2 + 3.
• n = 9 returns 3: you can write 9 as 9, 4 + 5, or 2 + 3 + 4.
• n = 15 returns 4: you can write 15 as 15, 7 + 8, 4 + 5 + 6, or 1 + 2 + 3 + 4 + 5.

The constraint is 1 <= n <= 10^9, so any brute-force approach that tries all possible sequences will be far too slow. You need a solution that runs in O(sqrt(n)) time.

Each row shows one valid decomposition of 15 into consecutive positive integers. The question is: how do you find all of them without checking every possible starting point and length?

The key insight

Suppose you have k consecutive integers starting at x. Their sum is:

x + (x+1) + (x+2) + ... + (x+k-1) = k*x + k*(k-1)/2

Set this equal to n:

k*x + k*(k-1)/2 = n

Solving for x:

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

For a valid sequence, x must be a positive integer. That means two conditions must hold:

1. n - k*(k-1)/2 must be positive (so x > 0)
2. n - k*(k-1)/2 must be divisible by k (so x is an integer)

You iterate k from 1 upward, checking both conditions. When k*(k-1)/2 >= n, the remainder is no longer positive and you stop. Since k*(k-1)/2 grows quadratically, the loop runs at most O(sqrt(n)) iterations.

The solution

def consecutiveNumbersSum(n):
    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

The loop tries every possible sequence length k starting from 1. For each k, it computes the remainder n - k*(k-1)/2. If that remainder is positive and divisible by k, then there exists a valid sequence of k consecutive integers starting at remainder // k. The loop terminates when k*(k-1)/2 >= n, because at that point the starting value would be zero or negative.

Visual walkthrough

Let's trace through consecutiveNumbersSum(15) to see the algorithm in action.

Out of the five values of k we checked, four produced valid decompositions. The only failure was k = 4, where the remainder 9 is not divisible by 4. The loop stops at k = 6 because 6*5/2 = 15, which is not less than n.

Complexity analysis

The O(sqrt(n)) time makes this efficient even for n = 10^9, where k reaches at most about 44,721 iterations. Each iteration does constant work: one multiplication, one subtraction, and one modulo check.

The building blocks

1. Arithmetic series formula

The sum of k consecutive integers starting at x equals k*x + k*(k-1)/2. This formula converts a variable-length summation problem into a closed-form expression. The same idea appears in problems involving triangular numbers, range sums, and any scenario where you need the sum of an arithmetic progression without actually iterating through it.

2. Divisibility as a search replacement

Instead of trying all possible starting points for each sequence length, you check whether a valid starting point exists by testing a single divisibility condition. This pattern, replacing enumeration with a mathematical existence check, is a powerful technique in number theory problems. You see it in problems like counting divisors, checking perfect squares, and factoring.

Edge cases

Before submitting, make sure your solution handles these:

• n = 1: the only representation is [1]. The loop checks k = 1: remainder is 1 - 0 = 1, which is divisible by 1. Then k = 2: k*(k-1)/2 = 1, which is not less than n = 1, so the loop stops. Answer: 1.

• Powers of 2 like n = 16: the only valid representation is the number itself. Powers of 2 have no odd divisors other than 1, so no multi-element consecutive sequence can sum to them. Answer: 1.

• Odd numbers like n = 15: odd numbers always have at least two representations (the number itself and a pair centered around n/2). They tend to have more valid decompositions than even numbers of similar size.

• Large n like n = 10^9: the loop runs about 44,721 iterations, well within time limits. Make sure you use integer division (//) to avoid floating-point precision issues.

From understanding to recall

You have seen how the arithmetic series formula transforms a search problem into a divisibility loop. The solution is short: one while loop, one modulo check, done. But under interview pressure, you need the formula x = (n - k*(k-1)/2) / k to come to mind instantly. You need to remember the two conditions (positive and divisible) and the stopping criterion (k*(k-1)/2 >= n).

Spaced repetition locks this in. You derive the formula from scratch today, write the loop again in two days, then four days, then a week. After a few rounds, you see "consecutive sum" and the arithmetic series formula appears without effort. The derivation becomes muscle memory.

Related posts

• Perfect Squares - Another math problem where you reduce a search to a formula involving square roots
• Factorial Trailing Zeroes - Counting factors with a tight loop instead of brute-force computation
• Pow(x, n) - Turning a linear brute-force into an efficient O(log n) solution through mathematical structure

CodeBricks breaks the consecutive numbers sum problem into its arithmetic series and divisibility-check building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a math decomposition question shows up in your interview, you do not reach for brute force. You reach for the formula.