Consecutive Numbers Sum

HARD

Description

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 <= 10⁹

Approaches

Checkout 3 different approaches to solve Consecutive Numbers Sum. Click on different approaches to view the approach and algorithm in detail.

Brute-force with Nested Loops

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.

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 Analysis

Time Complexity: 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 Complexity: O(1) - We only use a few variables to store the count and the current sum.

Pros and Cons

Pros:

Simple to understand and implement.

Cons:

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

Code Solutions

Checking out 3 solutions in different languages for Consecutive Numbers Sum. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Consecutive Numbers Sum

Patterns:

MathEnumeration