829. Consecutive Numbers Sum
Given an integer n, return the number of ways you can write n as the sum of consecutive positive integers.
- basic idea from sum [1…n] = n * (n + 1) / 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
int formula(int target, int k) {
return (target / k) + k;
}
bool verify(int target, int k) {
int alpha = formula(target, k);
return alpha & 1;
}
public:
int consecutiveNumbersSum(int n) {
int target = n * 2;
int res = 0;
for(int k = 1; k * k <= target; k++) {
if(target % k == 0 and verify(target, k)) {
res++;
}
}
return res;
}
};
|
- build up from this formula
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
int formula(int target, int k) {
return ((target / k) + k - 1) / 2;
}
bool verify(int target, int k) {
int alpha = formula(target, k);
return k * (2 * alpha - k + 1) == target;
}
public:
int consecutiveNumbersSum(int n) {
int target = n * 2;
int res = 0;
for(int k = 1; k * k <= target; k++) {
if(target % k == 0 and verify(target, k)) {
res++;
}
}
return res;
}
};
|
