#829
Consecutive Numbers Sum
Hard Number theory
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Count the ways to write n as a sum of one or more consecutive positive integers.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: in how many ways is n a sum of a run of consecutive positive numbers?
Why this works: a run of length k starting at x sums to k·x + k(k-1)/2. For a fixed k, solve for x and check it's a positive whole number. k only goes up to about √(2n).
Example: n = 9
k=1: 9 % 1 = 0 → [9]k=2: (9-1) % 2 = 0 → [4,5]k=3: (9-3) % 3 = 0 → [2,3,4]k=4: (9-6) % 4 ≠ 0answer: 3
✦Hints open one at a time
A run of k numbers starting at x sums to k·x + k(k-1)/2.
So for a fixed k, a valid x exists exactly when n - k(k-1)/2 is positive and divisible by k.
k(k-1)/2 must stay below n, so k only goes up to about √(2n).
↗Approach
Try every length k from 1 while k(k-1)/2 < n. For each, check whether (n - k(k-1)/2) % k == 0. Each success is one way.
</>Solution (Java)
class Solution {
public int consecutiveNumbersSum(int n) {
int ways = 0;
for (long k = 1; k * (k - 1) / 2 < n; k++) {
if ((n - k * (k - 1) / 2) % k == 0) ways++; // a positive start x exists
}
return ways;
}
}!Common mistake
Looping x over all starting values — that's O(n) or worse and times out for n up to 10^9.
Complexity
- Time: O(√n).
- Space: O(1).
