HardMathEnumerationUpdated Sep 2026

829. Consecutive Numbers Sum

Asked at Microsoft

Difficulty

Hard

Time

O(sqrt(n))

Space

O(1)

Pattern

Math

Companies

1

Problem

Given a positive integer n, count how many ways you can write n as a sum of consecutive positive integers.

A "way" is a choice of a starting number a and a length k, where the numbers a, a+1, ..., a+k-1 all add up to n. The length k must be at least 1, so n alone counts as one way. Different starting numbers or different lengths give different ways, even if the total is the same.

Return the number of ways, not the lists themselves.

Which runs add up to n?

run90k = 1: the single number 9 worksrun4501k = 2: 4 + 5 = 9 worksrun234012k = 3: 2 + 3 + 4 = 9 worksrun12340123k = 4: 1 + 2 + 3 + 4 = 10, too big — no run of length4 fits
For n = 9 we look for runs of consecutive positive integers whose total is 9.

Constraints

  • ●1 <= n <= 10^9

Examples

Example 1
Inputn = 5
Output2
Why5 itself is one way (k=1). Also 2 + 3 = 5, which is a=2, k=2. No other run works, so the answer is 2.
Example 2
Inputn = 9
Output3
Why9 alone works. 4 + 5 = 9 works. 2 + 3 + 4 = 9 works. That is three ways.
Example 3
Inputn = 15
Output4
Why15 alone, 7 + 8, 4 + 5 + 6, and 1 + 2 + 3 + 4 + 5 all equal 15. Four ways in total.

Asked At

1 companies
CompanyDifficulty
MicrosoftHardView all Microsoft questions →

How to Think About It

1

Brute force: for every starting number a and every length k, check if a + (a+1) + ... + (a+k-1) == n. The sum is k*a + k(k-1)/2. This is O(sqrt(n)^2) = O(n) which is too slow.

2

Key insight: the sum of k consecutive numbers starting at a is k*a + k(k-1)/2 = n. Rearranging: a = (n - k(k-1)/2) / k. For a valid solution, a must be a positive integer, meaning n - k(k-1)/2 must be divisible by k and the result must be > 0.

3

Bound on k: since a >= 1, we need k(k+1)/2 <= n, so k <= sqrt(2n). This means we only need to try k from 1 to sqrt(2n), giving O(sqrt(n)) time.

4

The count of ways equals the count of odd divisors of n. This is because n = k*a + k(k-1)/2 simplifies to 2n = k(2a+k-1), where k and (2a+k-1) have opposite parity. Each valid factorization of 2n into k and (2a+k-1) with k >= 1 gives a solution.

5

Edge cases: n=1 returns 1 (just [1]). n=2 returns 1 (just [2]). Large n up to 10^9 still works in O(sqrt(n)).

Optimal Approach

Step 1: Initialize count = 0.
Step 2: For k from 1 while k*(k+1)/2 <= n:

  • Compute remainder = n - k*(k-1)/2
  • If remainder > 0 and remainder % k == 0: count += 1
    Step 3: Return count.

Walkthrough with n=9:

  • k=1: remainder = 9-0 = 9. 9%1==0. Count=1.
  • k=2: remainder = 9-1 = 8. 8%2==0. Count=2.
  • k=3: remainder = 9-3 = 6. 6%3==0. Count=3.
  • k=4: remainder = 9-6 = 3. 3%4!=0.
  • k=5: 5*6/2=15 > 9. Stop.
  • Return 3.

Time: O(sqrt(n)). Space: O(1).

Try each length k, solve for the start a

k = 1, 2, 3, ...a = (n − k(k−1)/2) / ka positive integer? count itThe sum of k consecutive numbers starting at a is k*a+ k(k−1)/2, so a is determined by k.n = 9kavalid19yes24yes32yes40.75noThree valid rows, so the answer is 3.stop when k(k+1)/2 > nanswer = 3
For a fixed length k the start a is forced, so we just check whether it is a positive whole number.
ComplexityTime O(sqrt(n))Space O(1)We only try lengths k up to about sqrt(2n), and each check is a constant-time division.

What Trips People Up in Real Interviews

1

Trying to enumerate all possible starting numbers and lengths. The key is to fix k (length) and compute a directly.

2

Forgetting that a must be a positive integer (a >= 1). If the formula gives a <= 0 or a is not an integer, skip that k.

3

Off-by-one in the bound. Use k*(k+1)//2 <= n as the loop condition. Going one k too far wastes time but does not give wrong answers.

4

Confusing this with counting subsequences. This is about consecutive POSITIVE integers (not subsequences), and the order is fixed.

5

Not handling n=1 correctly. n=1 has exactly one representation: [1]. The formula gives k=1, a=1 which is valid.

Solution Code

O(sqrt(n)) time
def consecutiveNumbersSum(n):
    count = 0
    k = 1
    while k * (k + 1) // 2 <= n:
        rem = n - k * (k - 1) // 2
        if rem > 0 and rem % k == 0:
            count += 1
        k += 1
    return count

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Consecutive Numbers Sum problem?

Given a positive integer n, return the number of ways to write n as a sum of two or more consecutive positive integers. For example, n=9 can be written as 9, 4+5, 2+3+4, so the answer is 3.

How do you solve Consecutive Numbers Sum?

The optimal approach runs in O(sqrt(n)) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Consecutive Numbers Sum?

Consecutive Numbers Sum is asked at Microsoft. It is a hard difficulty problem.

What are common mistakes on Consecutive Numbers Sum?
  • Trying to enumerate all possible starting numbers and lengths. The key is to fix k (length) and compute a directly.
  • Forgetting that a must be a positive integer (a >= 1). If the formula gives a <= 0 or a is not an integer, skip that k.
  • Off-by-one in the bound. Use `k*(k+1)//2 <= n` as the loop condition. Going one k too far wastes time but does not give wrong answers.
  • Confusing this with counting subsequences. This is about consecutive POSITIVE integers (not subsequences), and the order is fixed.
  • Not handling n=1 correctly. n=1 has exactly one representation: [1]. The formula gives k=1, a=1 which is valid.