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:
2n is divisible by k.
x is 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
When:
k = 6
6 × 7 / 2 = 21
21 > 15
Stop.
Step 4
if (twoN % k != 0)
continue;
From the formula:
2n = k(2x + k - 1)
k must divide 2n.
Otherwise, no integer solution exists.
Example:
n = 15
2n = 30
k = 4
30 % 4 = 2
Not divisible.
Skip.
Step 5
int temp = twoN / k - k + 1;
This computes:
2x
because:
2x = (2n / k) - k + 1
Example:
n = 15
k = 3
temp = 30 / 3 - 3 + 1
= 10 - 3 + 1
= 8
Step 6
if (temp > 0 && temp % 2 == 0)
We check:
Since:
x = temp / 2
Example:
temp = 8
x = 4
Sequence:
4
5
6
Sum:
4 + 5 + 6 = 15
Increase count.
Step 7
count++;
One valid sequence has been found.
Step 8
return count;
Return the final answer.
Dry Run
Input
n = 15
count = 0
twoN = 30
k = 2
30 % 2 = 0
temp = 15 - 2 + 1
= 14
Even.
x = 7
Sequence:
7 + 8
count = 1
k = 3
30 % 3 = 0
temp = 10 - 3 + 1
= 8
x = 4
Sequence:
4 + 5 + 6
count = 2
k = 4
30 % 4 != 0
Skip.
k = 5
30 % 5 = 0
temp = 6 - 5 + 1
= 2
x = 1
Sequence:
1 + 2 + 3 + 4 + 5
count = 3
Stop.
k = 6
6 × 7 / 2 = 21
21 > 15
Answer
3
Dry Run for n = 10
twoN = 20
k = 2
20 % 2 = 0
temp = 10 - 2 + 1
= 9
Odd.
Invalid.
k = 3
20 % 3 != 0
Skip.
k = 4
20 % 4 = 0
temp = 5 - 4 + 1
= 2
Even.
x = 1
Sequence:
1 + 2 + 3 + 4
count = 1
Answer
1
Complexity Analysis
| Complexity | Value |
|---|
| Time Complexity | O(√n) |
| Space Complexity | O(1) |
Key Takeaways
The brute-force solution checks every possible sequence and takes O(n²) time.
The optimized approach uses the arithmetic progression formula to derive a condition for valid sequences.
By iterating only over possible sequence lengths (k) up to √n, we reduce the time complexity to O(√n) while using O(1) extra space.
This makes the solution efficient enough for the constraint n ≤ 10⁸.
Summary
To count the number of ways a positive integer can be expressed as the sum of two or more consecutive natural numbers, we can avoid brute-force enumeration by leveraging arithmetic progression properties. By deriving a mathematical condition for valid sequences and checking only feasible sequence lengths up to approximately √n, the solution achieves O(√n) time complexity and O(1) space complexity, making it efficient even for very large values of n.