面试问题 - 查找数字

Question

我刚刚在SE职位面试中得到了这个问题,除了暴力之外,我不太清楚如何回答这个问题:

给定自然数N,找到两个数字A和P,这样:

N = A +(A + 1)+(A + 2)+ ... +(A + P-1)

P应该是最大可能的.

例如:对于N = 14,A = 2且P = 4

N = 2 +(2 + 1)+(2 + 2)+(4 + 2-1)N = 2 + 3 + 4 + 5

有任何想法吗？

Answer 1

如果N是偶数/奇数,我们在总和中需要偶数/奇数个奇数.这已经是可能解决方案数量的一半.例如,对于N = 14,没有必要检查P是奇数的任何组合.

重写给定的公式,我们得到:

N = A + (A+1) + (A+2) + ... + (A+P-1)
    = P*A + 1 + 2 + ... + (P-1)
    = P*A + (P-1)P/2 *
    = P*(A + (P-1)/2)
    = P/2*(2*A + P-1)

最后一行意味着N必须可以被P/2整除,这也排除了许多可能性.例如,14只有这些除数:1,2,7,14.因此P的可能值为2,4,14和28.由于显而易见的原因,14和28被统治了(事实上,任何高于N/2的P都可以被忽略了).

这应该比蛮力方法快得多.

(*前n个自然数之和为n(n + 1)/ 2)