Problem Statement
Given a positive integer n, find the number of ways to represent it as the sum of two or more consecutive natural numbers.
Example 1
Input
n = 10
Output
1
Explanation
10 = 1 + 2 + 3 + 4
There is only one valid representation.
Example 2
Input
n = 15
Output
3
Explanation
15 = 1 + 2 + 3 + 4 + 5
15 = 4 + 5 + 6
15 = 7 + 8
Hence, the answer is 3.
Understanding the Problem
We need to count all possible sequences of consecutive natural numbers whose sum equals n.
For example:
n = 21
21 = 10 + 11
21 = 6 + 7 + 8
21 = 1 + 2 + 3 + 4 + 5 + 6
Answer = 3
Notice that:
Numbers must be consecutive.
Sequence length should be at least 2.
Starting number must be greater than 0.
Brute Force Approach
The simplest idea is:
Start from every number.
Keep adding consecutive numbers.
Stop when the sum exceeds
n.If the sum becomes exactly
n, increase the answer.
Example
For n = 15
Start from 1
1
1+2
1+2+3
1+2+3+4
1+2+3+4+5 = 15 ✔
Now start from 2
2
2+3
2+3+4
2+3+4+5
...
Continue until all starting numbers are checked.
Complexity
Time : O(n²)
Space: O(1)
This is too slow for n = 10^8.
Efficient Mathematical Approach
Suppose a sequence starts from x and contains k consecutive numbers.
x
x+1
x+2
...
x+k-1
Its sum is:
x + (x+1) + (x+2) + ... + (x+k-1)
Using the arithmetic progression formula:
Sum = k(2x + k - 1) / 2
Since the sum equals n:
n = k(2x + k - 1) / 2
Multiply both sides by 2:
2n = k(2x + k - 1)
Now solve for x:
x = (2n/k - k + 1) / 2
Now observe:
For every possible sequence length k, we only need to check whether:
2nis divisible byk.xis a positive integer.
If both are true, one valid sequence exists.
Why Do We Iterate Only Up to √n?
The smallest sum of k consecutive numbers is:
1 + 2 + 3 + ... + k
which equals:
k(k + 1) / 2
If this minimum sum becomes larger than n, no longer sequence is possible.
Therefore:
k(k + 1) / 2 <= n
This limits the loop to approximately:
√(2n)
Hence the algorithm runs in O(√n) time.
Java Solution
class Solution {
public int getCount(int n) {
int count = 0;
int twoN = 2 * n;
for (int k = 2; k * (k + 1) / 2 <= n; k++) {
// k must divide 2*n
if (twoN % k != 0)
continue;
int temp = twoN / k - k + 1;
// Starting number should be a positive integer
if (temp > 0 && temp % 2 == 0)
count++;
}
return count;
}
}
Code Explanation
Step 1
int count = 0;
Stores the number of valid ways.
Initially:
count = 0
Step 2
int twoN = 2 * n;
Instead of calculating 2*n repeatedly, we store it once.
Example:
n = 15
twoN = 30
Step 3
for (int k = 2; k * (k + 1) / 2 <= n; k++)
We try every possible sequence length.
For:
n = 15
Possible values are:
k = 2
k = 3
k = 4
k = 5

Join the conversation! Your thoughts help the community grow.