ConsecutiveNumbersSum [source code]
public class ConsecutiveNumbersSum {
static
/****************************************************************************/
class Solution {
public int consecutiveNumbersSum(int N) {
int res = 0;
for (int i = 1; i * (i + 1) / 2 <= N; i++) {
if ((N - i * (i + 1) / 2) % i == 0)
res++;
}
return res;
}
}
/****************************************************************************/
public static void main(String[] args) {
ConsecutiveNumbersSum.Solution tester = new ConsecutiveNumbersSum.Solution();
int[] inputs = {
5, 2,
9, 3,
15, 4,
855204, 8,
72316829, 8,
68188380, 16,
4072822, 8,
43156417, 4,
};
for (int i = 0; i < inputs.length / 2; i++) {
System.out.println (Printer.separator ());
int N = inputs[2 * i], ans = inputs[2 * i + 1], output = tester.consecutiveNumbersSum (N);
System.out.printf ("%d\n%s\n%d\n",
N, Printer.wrap (output + "", output == ans ? 92 : 91), ans
);
}
}
}
啊, 这个题目看起来有意思;
从9这个例子来看, 好像有点memo或者DP的感觉: 你第一个数字选择4的话, 你怎么知道5可以拆分成2+3呢?
感觉是有一个DP的树状结构的, 就是不知道怎么组织这个表格的设计;
另外一个念头, 任何一个连续的数字段, 实际上也可以用difference的思想: i..j实际上是1..j - 1..i-1;
但是这题求的不是和, 所以感觉这个difference的思路并没有太大帮助;
感觉好像可以利用这个difference的思想, 转换成为2sum问题; 尝试一下;
比如9 = sum(1..5) - sum(1..3). 这个最后就是在一个sum数列里面找2sum的问题;
不过有一个很难处理的地方, 你这个sum数组算到多大为止呢? 比如9, 实际上也有可能sum(1..10000) - sum(1..9999) = 9啊, 当然, 只是假设. 那不可能穷举到所有的; 这个好像就是这个问题的难点所在;
最起码, 如果你把这个加法问题转化为减法问题, 那么这个难点就很难攻克;
所以或许还是直接用加法拆分的思路比较好?
这题直接的搜索应该是能搜出来的;
哦不对, 减法的上限可以决定啊, sum(1..N) - sum(1..N-1) = N, 所以如果我们sum到了N, 能够算出来的diff最少是N(如果末尾的这个subarray更长, 这个diff就更大). 所以只要N达到我们input的这个N大小就行了;
算法是很好的, 但是被test4给break掉了, overflow了;
这个时候的代码:
class Solution {
public int consecutiveNumbersSum(int N) {
int[] sum_till = new int[N + 1];
int sum = 0;
Map<Integer, Integer> invert_sum = new HashMap<> ();
for (int i = 1; i <= N; i++) {
sum += i;
sum_till[i] = sum;
invert_sum.put (sum, i);
}
invert_sum.put (0, 0); // subtle but critical
int res = 0;
boolean added_self = false;
for (int i = 1; i <= N; i++) {
int prev = sum_till[i] - N;
if (invert_sum.containsKey (prev)) {
res++;
if (invert_sum.get (prev) == i - 1)
added_self = true;
}
}
return res + (added_self ? 0 : 1);
}
}
想要用long尝试一下, 但是感觉还是被他们想到了, 这个时候发现一个问题, sum这种数组根本不用去保存啊, 直接计算就行了; 而且我最后用的实际上只有这个invert, 所以干脆直接走一遍计算这个反向查询就行了?
更进一步, 有没有必要计算这个反向查询? 完全是数学公式的计算啊: sum(1..i) = (i + 1)i / 2, 你拿到一个sum, 你就是想知道一个i存不存在而已; 这个计算我以前是做过的;
好不容易解决掉了overflow问题, 居然TLE了? 我这个完全是线性的算法居然还是TLE了; 这题不讲理了;
TLE第一反应, 有没有什么快速直接的优化? 比如简单的prune?
这里有没有对称性?
被一个很大的68188380给TLE掉之后, 干脆就只要是这么大的, 就返回1, 然后就被test5给break掉了哈哈;
test6也是一样的;
线性的还能怎么样啊, 这题是不是只接受math解法啊;
倒序走i, 然后sum不够大的时候就直接退出, 过掉了test5和6, 但是又被4072822给TLE掉了: 这个case的有效sum区间肯定相当长;
满地爬的大case, 明显就是只接受数学解法了, 真的无语; 等于说这题想了这么多办法, 各种我会的技巧都用上了, 然后你最后只接受数学解法?
最后discuss看到的AC的算法全都是sublinear的, 那么我自己这个肯定是有问题的了; 这个时候的算法;
class Solution {
public int consecutiveNumbersSum(int N) {
int res = 0;
boolean added_self = false;
for (int i = N; i >= 1; i--) {
long sum_here = (long) ((i + 1) * 0.5 * i); // take in 0.5 first
if (sum_here < N)
break;
long prev_sum = sum_here - N;
long prev_end = f (prev_sum);
if (prev_end >= 0) {
res++;
if (prev_end == i - 1)
added_self = true;
}
}
return res + (added_self ? 0 : 1);
}
long f (long sum) {
long res = -1;
if (sum == 0)
res = 0;
else {
long root = (long) Math.sqrt (2 * sum);
if (root * (root + 1) == 2 * sum)
res = root;
else {
root++;
if (root * (root + 1) == 2 * sum)
res = root;
}
}
return res;
}
}
最后按照discuss1写的一个AC了, 速度是22(NA).
UNFINISHED
editorial
Approach #1: Brute Force [Time Limit Exceeded]
Intuition and Algorithm
For each starting number, we scan forward until we meet or exceed the target N. If we meet it, then it represents one way to write N as a sum of consecutive numbers.
For example, if N = 6, and we scan forward from 1, we'll get 1 + 2 + 3 = 6 which contributes to the answer. If we scan forward from 2, we'll get 2 + 3 + 4 (the first time that the sum is >= N) which is too big.
class Solution {
public int consecutiveNumbersSum(int N) {
int ans = 0;
for (int start = 1; start <= N; ++start) {
int target = N, x = start;
while (target > 0)
target -= x++;
if (target == 0) ans++;
}
return ans;
}
}
能把这个naive做法分析出来, 在真正面试过程当中应该也是有所帮助的; 包括这个复杂度, 也要讲对; N个起点, 每一个起点最多扫N;
Approach #2: Mathematical (Naive) [Time Limit Exceeded]
其实这里看到这个N的表达方式, 想到找这个k, 实际上就是已经很大的一步了;
class Solution {
public int consecutiveNumbersSum(int N) {
// 2N = k(2x + k + 1)
int ans = 0;
for (int k = 1; k <= 2*N; ++k)
if (2 * N % k == 0) {
int y = 2 * N / k - k - 1;
if (y % 2 == 0 && y >= 0)
ans++;
}
return ans;
}
}
所以我自己的方法顶多也是属于naive math的范畴, 是O(N)的;
这个方法的一个问题还是在于, 还是局限在找到这个k, 不对, 他这里的k的定义不一样, 他这里的x是base, k是offset; 下面的discuss1, k是base, i是offset;
实际上我重新看了一下这个解法的写法, 跟discuss1是有点类似的, 不过他没有优化k(offset)的搜索范围: discuss1就是把这个范围缩小到sqrtN而已;
Approach #3: Mathematical (Fast) [Accepted]
第三段看起来可能有点奇怪, 其实这个就是从2N里面提取alpha个2, 然后剩下的是一个odd的M的过程, 这里alpha和M都是没有确定的, 有无限多种的可能性;
另外为什么说这里guaranteed to be strictly larger? 2^alpha乘以odd number M的一个因子, 跟另外一个因子对比, 肯定不可能相等, 是这个意思吧? 这个是怎么证明的? 首先M里面肯定没有2了, a和b里面也肯定都没有2, 所以a和b都是odd; 那么2^alpha跟a乘起来, 得到的是even, 剩下的b肯定是odd, 所以两个term不可能相等; 这个也是为什么他要说因为 alpha >= 1, 因为只有这样才能保证2^alpha * a至少有一个2, 能够和b形成一个奇偶对比;
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;
while (N % d == 0) {
N /= d;
e++;
}
ans *= e + 1;
d += 2;
}
if (N > 1) ans <<= 1;
return ans;
}
}
然后代码本身应该是不难理解, d代表从3开始的所有可能的odd factor, step是2, 然后上限是平方根; 如果要你统计odd factor, 这个要能够想到怎么做;
对于每一个这样的d, 把他从N里面拿走, 同时数一下有多少个;
然后几个边界情况, 包括最后N > 1的这个判断什么的, 就没有仔细去看了;
总体来说这个方法也不难, 不过感觉并不如discuss1好理解和简单;
editorial not necessarily the best solution
这个也是确立了我长久以来不太确定的一个东西, 就是editorial, 包括这里甚至是awice写的editorial, 实际上也未必就是最好的答案; 之前有一道tile的题, 就被awice的解法给坑过一次(跟discuss的解法根本没法比), 这里见证了, awice又一次有点跑偏.
现在这个时间段我时间很紧张, 所以没有办法痛快的把所有的discuss解法都看一遍; 但是我觉得, 有editorial的题目, 哪怕是把discuss1给看一眼, 知道跟editorial比起来到底怎么样, 也好过完全不看; 至少知道有这么个alternative;
N can be expressed as k + 1, k + 2, ..., k + i, which is
N = k i + (i + 1) i / 2.Since N can always be written as N, we can start from i = 2, ans = 1.
public int consecutiveNumbersSum(int N) {
int ans = 1;
for (int i = 2; i * (i + 1) / 2 <= N; ++i) {
if ((N - i * (i + 1) / 2) % i == 0) ++ans;
}
return ans;
}
这个方法牛逼; 首先我diff of sum的思路, 是没有错的; 只不过我动笔还是太早了; 这题需要他们这样非常严谨的观察, 才最后得到这个思路;
他这个其实都没有借助图形什么的去理解, 就是单纯的分析规律: sum (k + 1, k + 2, ..., k + i). 这里k是一个类似base, 然后1..i类似一个offset; 这个表示完全没有问题;
看完了这个只能说这题还是我自己想太复杂了; 中途的锻炼还是很有意思的; 不过对于解题本身, 是有点丢人; 难怪这题后来看contest结果那么多人做出来了; 一个明显的数学规律 (而不是让人痛恨的数学定理类)的题目, 结果我没做出来, 给中国人丢人了;
真的是, 这题还是做急了;
你看到, 这题只要真正的思路正确, 最后实际上连用long来避免overflow都是不需要的;
uwi: 我折腾这么半天, 人家两分钟好吧
class Solution {
boolean ok(int d, int n)
{
int u = n/d;
int a = u-d+1;
if(a % 2 != 0)return false;
return a > 0;
}
public int consecutiveNumbersSum(int n) {
// a,a+d-1
// (2a+d-1)/2*d = n
n *= 2;
int ct = 0;
for(int d = 1;(long)d*d <= n;d++){
if(n % d == 0){
if(ok(d, n))ct++;
if(d*d < n && ok(n/d, n))ct++;
}
}
return ct;
}
}
明显是哪里粘贴了什么代码来的, 看来是做过的;
感觉有点数学的东西有点多, 看不懂;
对了, 最简单的一个, 他这里的d是搜索到平方根位置, 这个是我可以学的啊; 对啊;
最后也没有看懂这个代码是在干什么; 首先肯定应该不是在count odd factor这种; 如果是用的类似discuss1的思路, 感觉又太复杂了;
Problem Description
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.
Difficulty:Medium
Total Accepted:658
Total Submissions:3.4K
Contributor:lee215
Related Topics
math