Consecutive Numbers Sum
Problem
Given an integer n, return the number of ways to write n as the sum of consecutive positive integers.
n = 93def consecutiveNumbersSum(n):
count = 0
k = 1
while k * (k + 1) // 2 <= n:
if (n - k * (k - 1) // 2) % k == 0:
count += 1
k += 1
return count
function consecutiveNumbersSum(n) {
let count = 0, k = 1;
while ((k * (k + 1)) / 2 <= n) {
if ((n - (k * (k - 1)) / 2) % k === 0) count++;
k++;
}
return count;
}
class Solution {
public int consecutiveNumbersSum(int n) {
int count = 0;
for (int k = 1; (long)k * (k + 1) / 2 <= n; k++) {
if ((n - k * (k - 1) / 2) % k == 0) count++;
}
return count;
}
}
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int consecutiveNumbersSum(int n) {
int count = 0;
for (int k = 1; (long long)k * (k + 1) / 2 <= n; k++) {
if ((n - k * (k - 1) / 2) % k == 0) count++;
}
return count;
}
};
Explanation
We count how many ways n can be written as a run of consecutive positive integers. The clever part is turning that into a simple divisibility test for each possible run length k.
A run of k numbers starting at a sums to k·a + k(k-1)/2. Setting that equal to n and solving gives a = (n - k(k-1)/2) / k. The run is valid exactly when this a comes out a positive integer.
So for each k we just check whether (n - k(k-1)/2) is divisible by k. If it is, we found a valid run and bump count.
We stop once k(k+1)/2 > n, because the smallest possible run of length k (starting at 1) already exceeds n. That keeps the loop short, around sqrt(n) steps.
Example: n = 9. k=1 works (just 9), k=2 works (4+5), k=3 works (2+3+4), and k=4 fails. So the answer is 3.