Ways to Express as Sum of Consecutives

Time: O(n)

Space: O(1)

Problem Overview

Count how many ways n equals a sum of two or more consecutive positive integers (e.g.

Intuition

Count how many ways n equals a sum of two or more consecutive positive integers (e.g. 9 = 2+3+4 = 4+5). Maintain a sliding window over 1,2,3,…: expand the right end, shrink the left while the sum is too large, and count every time the window sum hits n.

Algorithm

1Initialize sum = 0, left marker x = 1, count = 0.
2For right r = 1 … n: if sum == n, increment count (window [x .. r−1] is a valid consecutive run).
3Add r to sum.
4While sum > n: subtract x and increment x (shrink from the left).
5Return count.

Example Walkthrough

Input: n = 9

1. Grow the window until sum exceeds 9, then shrink.
2. Window 2+3+4 = 9 → count once.
3. Window 4+5 = 9 → count again.
4. Trivial “9 alone” is never counted because the check runs before adding r and the loop stops at r = n.

Output: 2

Common Pitfalls

• Require at least two terms — the sliding-window check before adding r naturally skips the single-term representation.
• Shrink with while (sum > n), not a single if — one shrink may not be enough.
• O(√n) math alternative: count odd divisors of n minus 1; the window solution is O(n) and matches this code.

Ways to Express as Sum of Consecutives.java

Java

// Approach: Sliding window over consecutive positives 1,2,3,… — expand right, shrink left
// while sum > n; whenever the window sum equals n, count one way (length ≥ 2 automatically).
// Time: O(n) Space: O(1)

class Solution {

    public int getCount(int n) {
        int sum = 0, cnt = 0, x = 1;
        for (int r = 1; r <= n; r++) {
            if (sum == n) {
                cnt++;
            }
            sum += r;
            while (sum > n) {
                sum -= x;
                x += 1;
            }
        }
        return cnt;
    }
};

Was this solution helpful?