LeetCode 829 - Consecutive Numbers Sum

LeetCode Problem 829

Difficulty: 🔴 Hard
Topics: Math, Enumeration

Solution

Problem Understanding

The problem asks us to determine in how many distinct ways an integer n can be expressed as a sum of consecutive positive integers. In other words, we need to find sequences of integers starting from some positive number x and having length k such that the sum of that sequence equals n. The sequences must consist of at least one number, and all numbers must be positive.

The input n is a single integer between 1 and 10^9. This large upper limit implies that a naive approach that tries every possible sequence could be too slow, and an optimized mathematical approach is required. The expected output is an integer representing the number of valid sequences.

Important edge cases include very small numbers like n = 1, where the sequence contains only one number, and large numbers near 10^9, which could stress inefficient loops. The problem guarantees that n is positive, so we do not have to handle zero or negative input.

Approaches

Brute Force Approach

A naive brute-force solution would involve iterating over every possible starting number x and summing consecutive integers until the sum either equals n or exceeds it. If the sum equals n, we count it as a valid sequence. While this approach is correct, it is inefficient for large n because the number of potential sequences to check can grow linearly with n. This results in a time complexity of approximately O(n^2), which is not feasible given the constraints.

Optimal Approach

The key insight is to express n as a sum of k consecutive numbers using a formula. If a sequence starts with x and has length k, the sum is:

n = x + (x + 1) + (x + 2) + ... + (x + k - 1)
  = k*x + k*(k - 1)/2

Rewriting, we get:

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

x must be a positive integer, so (n - k*(k - 1)/2) must be divisible by k. This reduces the problem to iterating over possible lengths k and checking this divisibility condition. Since k*(k - 1)/2 grows quadratically, we only need to consider values of k such that k*(k - 1)/2 < n. This reduces the search space significantly and yields an efficient solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(1)	Check every possible starting number and sequence length
Optimal	O(sqrt(n))	O(1)	Iterate possible sequence lengths and check divisibility

Algorithm Walkthrough

1. Initialize a counter count to zero to track valid sequences.
2. Iterate k from 1 upwards while k*(k - 1)/2 < n. This ensures we only consider lengths that could possibly sum to n.
3. For each k, compute n - k*(k - 1)/2. If this value is divisible by k, it means there exists a positive integer starting number x such that the sum of k consecutive numbers equals n.
4. If the divisibility condition is met, increment count by 1.
5. Return count after the loop completes.

Why it works: The formula x = (n - k*(k - 1)/2) / k captures all possible sequences that sum to n. Iterating through feasible values of k guarantees that we examine all potential sequence lengths without checking every starting number individually. The divisibility check ensures that x is a positive integer, so all counted sequences are valid.

Python Solution

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:
                count += 1
            k += 1
        return count

The implementation initializes a counter for valid sequences and iterates over possible sequence lengths. For each length, it computes the adjusted sum (n - k*(k - 1)//2) and checks if it is divisible by k. If so, it increments the count. The loop terminates once k*(k - 1)/2 reaches or exceeds n, ensuring efficiency.

Go Solution

func consecutiveNumbersSum(n int) int {
    count := 0
    k := 1
    for k*(k-1)/2 < n {
        if (n - k*(k-1)/2) % k == 0 {
            count++
        }
        k++
    }
    return count
}

The Go implementation mirrors the Python version closely. Integer division automatically floors the result, so k*(k-1)/2 produces the intended integer result. The loop and condition checks are straightforward and handle large integers correctly since Go's int type can hold values up to 2^31-1 for typical LeetCode constraints.

Worked Examples

Example 1: n = 5

k	k*(k-1)/2	n - k*(k-1)/2	divisible by k?	count
1	0	5	Yes	1
2	1	4	Yes	2
3	3	2	No	2
4	6	-1	-	2

Result: 2

Example 2: n = 9

k	k*(k-1)/2	n - k*(k-1)/2	divisible by k?	count
1	0	9	Yes	1
2	1	8	Yes	2
3	3	6	Yes	3
4	6	3	No	3
5	10	-1	-	3

Result: 3

Example 3: n = 15

k	k*(k-1)/2	n - k*(k-1)/2	divisible by k?	count
1	0	15	Yes	1
2	1	14	Yes	2
3	3	12	Yes	3
4	6	9	No	3
5	10	5	Yes	4
6	15	0	Yes	5 (but x=0 not positive, ignored)

Result: 4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(sqrt(n))	Maximum k satisfies k*(k-1)/2 < n, so k is approximately sqrt(2n), giving O(sqrt(n)) iterations.
Space	O(1)	Only a few integer variables are used; no extra space is required.

The time complexity is driven by the quadratic growth of k*(k-1)/2. Since we only need to iterate up to sqrt(2n), this approach is efficient even for n up to 10^9. The space complexity is constant because no dynamic data structures are needed.

Test Cases

# Basic examples
assert Solution().consecutiveNumbersSum(5) == 2  # 2+3, 5
assert Solution().consecutiveNumbersSum(9) == 3  # 2+3+4, 4+5, 9
assert Solution().consecutiveNumbersSum(15) == 4 # 1+2+3+4+5, 4+5+6, 7+8, 15

# Edge cases
assert Solution().consecutiveNumbersSum(1) == 1  # only 1 itself
assert Solution().consecutiveNumbersSum(2) == 1  # only 2 itself
assert Solution().consecutiveNumbersSum(3) == 2  # 3, 1+2

# Large number
assert Solution().consecutiveNumbersSum(1000000000) > 0  # ensure it handles large input

Test	Why
5, 9, 15	Provided examples to verify correctness
1, 2, 3	Smallest edge cases to ensure correct handling of single numbers and short sequences
1000000000	Tests performance on maximum input

Edge Cases

The first edge case is when n is 1. Only one sequence exists, consisting of the number itself. This could cause a naive loop that assumes k ≥ 2 to miss the single-number sequence. The implementation correctly handles this because the loop starts with k = 1.

The second edge case occurs when n is a power of 2, such as 8. Powers of 2 often have fewer representations as sums of consecutive numbers.