Scale Engineer

Consecutive Numbers Sum

Hard
#0783Time: O(n^2) - In the worst case, the outer loop runs `n` times, and the inner loop can also run up to `n` times, leading to a quadratic time complexity. This is too slow for `n` up to 10^9.Space: O(1) - We only use a few variables to store the count and the current sum.
Patterns
MathEnumeration

Prompt

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

 

Example 1:

Input: n = 5
Output: 2
Explanation: 5 = 2 + 3

Example 2:

Input: n = 9
Output: 3
Explanation: 9 = 4 + 5 = 2 + 3 + 4

Example 3:

Input: n = 15
Output: 4
Explanation: 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5

 

Constraints:

  • 1 <= n <= 109

Approaches

3 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. We try every possible starting positive integer and, for each, we build a sum of consecutive integers. If the sum equals n, we count it as one way.

Algorithm

  • Initialize count = 0.
  • Iterate with an outer loop for start from 1 to n.
  • Inside the outer loop, initialize currentSum = 0.
  • Start an inner loop for j from start to n.
  • Add j to currentSum.
  • If currentSum == n, increment count and break the inner loop.
  • If currentSum > n, break the inner loop.
  • Return count.

Walkthrough

We can use two nested loops. The outer loop iterates through all possible starting numbers start from 1 up to n. The inner loop adds consecutive numbers to start, forming a currentSum.

  • If currentSum equals n, we've found a valid sequence, so we increment our counter and break the inner loop to try the next start.
  • If currentSum exceeds n, the current sequence is too large, so we break the inner loop and move to the next start. This method is very intuitive but its inefficiency makes it impractical for large values of n.
class Solution {    public int consecutiveNumbersSum(int n) {        int count = 0;        for (int start = 1; start <= n; start++) {            long currentSum = 0;            for (int j = start; j <= n; j++) {                currentSum += j;                if (currentSum == n) {                    count++;                    break;                }                if (currentSum > n) {                    break;                }            }        }        return count;    }}

Complexity

Time

O(n^2) - In the worst case, the outer loop runs `n` times, and the inner loop can also run up to `n` times, leading to a quadratic time complexity. This is too slow for `n` up to 10^9.

Space

O(1) - We only use a few variables to store the count and the current sum.

Trade-offs

Pros

  • Simple to understand and implement.

Cons

  • Extremely inefficient and will result in a 'Time Limit Exceeded' error for the given constraints.

Solutions

class Solution {public  int consecutiveNumbersSum(int n) {    n <<= 1;    int ans = 0;    for (int k = 1; k * (k + 1) <= n; ++k) {      if (n % k == 0 && (n / k + 1 - k) % 2 == 0) {        ++ans;      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem