Problem Description

Given a positive integer n, find the number of ways it can be written as the sum of consecutive positive integers. Each sequence must consist of at least one integer, and the integers must be positive and consecutive. For example, 9 can be written as 2 + 3 + 4, 4 + 5, or just 9 itself.

Your task is to return the total number of possible ways to express n as the sum of one or more consecutive positive integers.

• Each sequence must use distinct, consecutive, positive numbers.
• Sequences with only one number (i.e., n itself) are valid.
• Sequences cannot reuse elements; each integer in a sequence must appear only once.
• Input: n (1 ≤ n ≤ 10⁹)
• Output: An integer representing the number of ways.

Thought Process

To solve this problem, let's first think about what it means to write n as the sum of consecutive positive integers. For example, for n = 9:

• 9 = 2 + 3 + 4
• 9 = 4 + 5
• 9 = 9

The brute-force way would be to try all possible sequences of consecutive numbers and check which ones sum to n. However, this would be too slow for large n. So, we need to look for a mathematical pattern or formula that helps us count the number of valid sequences efficiently.

Let's observe that the sum of k consecutive numbers starting from x is:
n = x + (x+1) + (x+2) + ... + (x+k-1) = kx + k(k-1)/2
Rearranged: n = kx + k(k-1)/2. So, n - k(k-1)/2 = kx.
Thus, (n - k(k-1)/2) must be divisible by k and x > 0.

This gives us a way to check for each possible value of k (number of terms in the sequence) whether there's a valid x (start of the sequence) that makes the sum equal to n.

Solution Approach

Let's break down the steps to efficiently count the number of ways to write n as the sum of consecutive positive integers:

1. For each possible value of k (sequence length) starting from 1, compute k(k-1)/2 (sum of the first k-1 integers).
2. Check if n - k(k-1)/2 is positive; if not, stop (as sequences longer than this can't start with a positive integer).
3. If n - k(k-1)/2 is divisible by k, then there exists a positive integer x such that the sequence x, x+1, ..., x+k-1 sums to n.
4. For each valid k, increment the count.
5. Continue until k(k-1)/2 < n.

This approach is efficient because the value k(k-1)/2 grows quadratically, so the loop runs only up to about O(√2n) iterations.

Example Walkthrough

Let's illustrate the process with n = 15:

• k = 1: 15 - 0 = 15; 15 % 1 == 0 ⇒ valid (sequence: [15])
• k = 2: 15 - 1 = 14; 14 % 2 == 0 ⇒ valid (sequence: [7, 8])
• k = 3: 15 - 3 = 12; 12 % 3 == 0 ⇒ valid (sequence: [4, 5, 6])
• k = 4: 15 - 6 = 9; 9 % 4 == 1 ⇒ not valid
• k = 5: 15 - 10 = 5; 5 % 5 == 0 ⇒ valid (sequence: [1, 2, 3, 4, 5])
• k = 6: 15 - 15 = 0; 0 % 6 == 0 ⇒ valid (sequence: [0, 1, 2, 3, 4, 5]) but 0 is not positive, so skip
• k = 7: 15 - 21 = -6; negative, stop

So, there are 4 valid ways: [15], [7,8], [4,5,6], [1,2,3,4,5].

Time and Space Complexity

Brute-force approach:
For each possible starting number, try all possible sequence lengths, summing up until the total is at least n. This is O(n) or worse, which is too slow for large n.

Optimized approach:
We only need to check up to k where k(k-1)/2 < n. Since k^2 grows quickly, the number of iterations is about O(√n).
Time Complexity: O(√n)
Space Complexity: O(1) (just a counter variable)

Summary

The key insight is transforming the problem into a mathematical equation relating n, the sequence length k, and the starting number x. By iterating over possible sequence lengths and checking divisibility, we can efficiently count the valid consecutive sums in O(√n) time. This avoids brute-force enumeration and leverages arithmetic properties for an elegant and efficient solution.

Code Implementation

class Solution:
    def consecutiveNumbersSum(self, n: int) -> int:
        count = 0
        k = 1
        while k * (k - 1) // 2 < n:
            if (n - k * (k - 1) // 2) % k == 0:
                x = (n - k * (k - 1) // 2) // k
                if x > 0:
                    count += 1
            k += 1
        return count
      

class Solution {
public:
    int consecutiveNumbersSum(int n) {
        int count = 0;
        for (long long k = 1; k * (k - 1) / 2 < n; ++k) {
            if ((n - k * (k - 1) / 2) % k == 0) {
                int x = (n - k * (k - 1) / 2) / k;
                if (x > 0)
                    ++count;
            }
        }
        return count;
    }
};
      

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

var consecutiveNumbersSum = function(n) {
    let count = 0;
    let k = 1;
    while (k * (k - 1) / 2 < n) {
        if ((n - k * (k - 1) / 2) % k === 0) {
            let x = (n - k * (k - 1) / 2) / k;
            if (x > 0) count++;
        }
        k++;
    }
    return count;
};