Consecutive Numbers Sum - Practice Coding Problems

Consecutive Numbers Sum - Problem

Math Enumeration Hard

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

A consecutive sequence means the integers are in order: 1, 2, 3 or 5, 6, 7, 8, etc.

Example: n = 9 can be written as:

9 (single number)
4 + 5 (two consecutive numbers)
2 + 3 + 4 (three consecutive numbers)

So the answer is 3 ways.

Input & Output

Example 1 — Basic Case

$ Input: n = 9

› Output: 3

💡 Note: Three ways: 9 (single), 4+5 (two consecutive), 2+3+4 (three consecutive)

Example 2 — Small Number

$ Input: n = 15

› Output: 4

💡 Note: Four ways: 15, 7+8, 4+5+6, 1+2+3+4+5

Example 3 — Power of 2

$ Input: n = 8

› Output: 1

💡 Note: Only one way: 8 (powers of 2 can only be expressed as single number)

Constraints

1 ≤ n ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Given n = 9

Find Sequences

Look for consecutive number sequences that sum to 9

Count Ways

Return total number of valid sequences

Key Takeaway

🎯 Key Insight: Use arithmetic sequence formula to check if each sequence length can produce valid consecutive integers

Asked in

G Google 25 M Microsoft 18

The key insight is using the arithmetic sequence formula: sum of k consecutive numbers starting at a is k×a + k×(k-1)/2 = n. We solve for a and check if it's a positive integer. Best approach uses mathematical formula with Time: O(√n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Formula	O(√n)	O(1)	Use arithmetic sequence formula to find valid sequences directly
Brute Force - Try All Sequences	O(n²)	O(1)	Try every possible starting number and sequence length

Mathematical Formula — Algorithm Steps

For each sequence length k from 1 to sqrt(2*n)
Calculate a = (n - k*(k-1)/2)/k
If a is positive integer, increment count
Stop when a becomes non-positive

Visualization

Tap to expand

Step-by-Step Walkthrough

Formula

Sum = k*a + k*(k-1)/2 = n

Solve for a

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

Check integer

If a is positive integer, count++

Code -

solution.c — C

#include <stdio.h>

int solution(int n) {
    int count = 0;
    int k = 1;
    while (1) {
        // For k consecutive numbers starting at a:
        // Sum = k*a + k*(k-1)/2 = n
        // So a = (n - k*(k-1)/2) / k
        int numerator = n - k * (k - 1) / 2;
        if (numerator <= 0) {
            break;
        }
        if (numerator % k == 0) {
            count++;
        }
        k++;
    }
    return count;
}

int main() {
    int n;
    scanf("%d", &n);
    int result = solution(n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(√n)

Loop runs until a becomes non-positive, which happens around √(2n)

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables for calculations

✓ Linear Space

28.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Formula — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler