Formatted question description: https://leetcode.ca/all/829.html
829. Consecutive Numbers Sum (Hard)
Given a positive integer N
, how many ways can we write it as a sum of consecutive positive integers?
Example 1:
Input: 5 Output: 2 Explanation: 5 = 5 = 2 + 3
Example 2:
Input: 9 Output: 3 Explanation: 9 = 9 = 4 + 5 = 2 + 3 + 4
Example 3:
Input: 15 Output: 4 Explanation: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5
Note: 1 <= N <= 10 ^ 9
.
Companies:
Visa
Related Topics:
Math
Solution 1.
The sum of Arithmetic Progression (AP) is:
S = an + n(n1)d/2
where a
is the first element, n
is the count of elements, d
is the common difference.
In our case, S = N
, d = 1
so we have:
a = (N  n(n1)/2) / n
So we can traverse from n = 1
to n = N
to get a
, but they need to satisfy the following requirements:
a = (N  n(n1)/2) / n >= 1
so2N  n^2 + n >= 2n
,n(n+1) <= 2N
. Forn >= 1
,n(n+1) > n^2
son^2 < 2N
,n < sqrt(2N)
. ForN >= 1
,n < sqrt(2N)
is the same or tighter thann <= N
, so we can simply usen(n+1) <= 2N
as the upper bound. The last element
a + n  1 <= N
so(N  n(n1)/2)/n + n  1 <= N 2N  n(n1) + 2n(n1) <= 2nN n(n1) <= 2(n1)N n = 1 or n <= 2N
This is useless.
In sum, we traverse from n = 1
to n(n+1) <= 2N
, and if N  n(n1)/2
can be divided by n
, we can increment the count.
// OJ: https://leetcode.com/problems/consecutivenumberssum/
// Time: O(sqrt(N))
// Space: O(1)
class Solution {
public:
int consecutiveNumbersSum(int N) {
int ans = 0;
for (int n = 1; n * (n + 1) <= 2 * N; ++n) {
int a = N  n * (n  1) / 2;
if (a % n == 0) ++ans;
}
return ans;
}
};
Solution 2.
There are lots of multiplication in Solution 1. Is it possible to reduce them?
If we let n(n+1)
as s
. In the previous loop, s' = n(n1)
, s  s' = 2n
. So we can change the multiplication to addition.
Now let s = n(n+1)/2
, the upper bound of n
will be s <= N
. In each step, we do s += n
. And the a
can be N  s + n
now. We can further simply a % n == 0
to (N  s) % n == 0
since if (N  s + n) % n == 0
then (N  s) % n == 0
// OJ: https://leetcode.com/problems/consecutivenumberssum/
// Time: O(sqrt(N))
// Space: O(1)
class Solution {
public:
int consecutiveNumbersSum(int N) {
int ans = 0, n = 1, s = 1;
for (; s <= N; s += ++n) {
if ((N  s) % n == 0) ++ans;
}
return ans;
}
};
Solution 3.
Assume N=(x+1)+(x+2)+...+(x+k)
, where x >= 0
, k >= 1
.
We have 2N=k(2x+k+1)
, which has two factors, k
and 2x+k+1
, one of which is odd number and another is even. So the question now is how many ways to factor 2N
into one even and one odd number.
Assume 2N=2^t * M
, where M
is odd. If we factor M = a * b
, then multiply 2^t
to one of them will yield the even number. So the question now becomes how many ways to factor the odd part of N
.
If N = 3*3*3*5*5
, how many ways to factor N
into two numbers?
For one number, we can pick 0 to 3 3
s, and 0 to 2 5
s, so we have 4 * 3 = 12 options.
Here you can see the answer is multiplication of 1 + {count of a factor}
.
To get the count, we can start from d = 3
to d * d <= N
with increment 2, and try to divide N
with d to count the occurrance of d
in N
. If the count is c
, we multiply 1 + c
to answer.
But what if there is a factor greater than sqrt(N)
? In this case it have to be a prime number and there will be only one of it. So if eventually N > 1
, we multiply 2
to answer.
// OJ: https://leetcode.com/problems/consecutivenumberssum/
// Time: O(sqrt(N))
// Space: O(1)
// Ref: https://leetcode.com/problems/consecutivenumberssum/solution/
class Solution {
public:
int consecutiveNumbersSum(int N) {
while ((N & 1) == 0) N >>= 1;
int ans = 1, d = 3;
while (d * d <= N) {
int e = 0;
for (; N % d == 0; N /= d, ++e);
ans *= e + 1;
d += 2;
}
if (N > 1) ans <<= 1;
return ans;
}
};
Java

class Solution { public int consecutiveNumbersSum(int N) { int max = (int) Math.sqrt(N * 2); int count = 0; for (int i = 1; i <= max; i++) { if (i % 2 == 1) { if (N % i == 0) count++; } else { if (N % i != 0 && N * 2 % i == 0) count++; } } return count; } }

// OJ: https://leetcode.com/problems/consecutivenumberssum/ // Time: O(sqrt(N)) // Space: O(1) class Solution { public: int consecutiveNumbersSum(int N) { int ans = 0; for (int n = 1; n * (n + 1) <= 2 * N; ++n) { int a = N  n * (n  1) / 2; if (a % n == 0) ++ans; } return ans; } };

print("Todo!")