What is the Consecutive Numbers Sum problem?

The problem asks you to determine how many ways a number can be written as the sum of consecutive positive integers, with at least two integers in the sum.

How do I approach solving this problem?

Start by using the sum formula for consecutive integers and enumerate possible lengths for the sequences. Check if a valid starting integer exists for each length.

What is the time complexity of this solution?

The time complexity is O(sqrt(n)), as we iterate through possible sequence lengths up to the square root of n.

Why do we stop when k exceeds sqrt(n)?

Once the length of the sequence exceeds the square root of n, the sum would exceed n, making further checks unnecessary.

What are some common pitfalls in this problem?

Common mistakes include overlooking the requirement for positive starting integers, misusing the sum formula, and not optimizing by stopping early.

#829

Hard

auto_awesome数学·结合·enumeration

LeetCode 题解工作台

连续整数求和

给定一个正整数 n ，返回连续正整数满足所有数字之和为 n 的组数。示例 1: 输入: n = 5 输出: 2 解释: 5 = 2 + 3，共有两组连续整数([5],[2,3])求和后为 5。示例 2: 输入: n = 9 输出: 3 解释: 9 = 4 + 5 = 2 + 3 + 4 示…

数学枚举

题目描述

给定一个正整数 n，返回 连续正整数满足所有数字之和为 n 的组数 。

示例 1:

输入: n = 5
输出: 2
解释: 5 = 2 + 3，共有两组连续整数([5],[2,3])求和后为 5。

示例 2:

输入: n = 9
输出: 3
解释: 9 = 4 + 5 = 2 + 3 + 4

示例 3:

输入: n = 15
输出: 4
解释: 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5

提示:

1 <= n <= 10⁹

lightbulb

解题思路

方法一：数学推导

连续正整数构成一个公差 $d = 1$ 的等差数列。我们假设等差数列的第一项为 $a$ ，项数为 $k$ ，那么 $n = (a + a + k - 1) \times k / 2$ ，即 $n \times 2 = (a \times 2 + k - 1) \times k$ 。这里我们可以得出 $k$ 一定能整除 $n \times 2$ ，并且 $(n \times 2) / k - k + 1$ 一定是偶数。

由于 $a \geq 1$ ，所以 $n \times 2 = (a \times 2 + k - 1) \times k \geq k \times (k + 1)$ 。

综上，我们可以得出：

$k$ 一定能整除 $n \times 2$ ；
$k \times (k + 1) \leq n \times 2$ ；
$(n \times 2) / k - k + 1$ 一定是偶数。

我们从 $k = 1$ 开始枚举，当 $k \times (k + 1) > n \times 2$ 时，我们可以结束枚举。在枚举的过程中，我们判断 $k$ 是否能整除 $n \times 2$ ，并且 $(n \times 2) / k - k + 1$ 是否是偶数，如果是则满足条件，答案加一。

枚举结束后，返回答案即可。

时间复杂度 $O(\sqrt{n})$ ，其中 $n$ 为给定的正整数。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def consecutiveNumbersSum(self, n: int) -> int:
        n <<= 1
        ans, k = 0, 1
        while k * (k + 1) <= n:
            if n % k == 0 and (n // k + 1 - k) % 2 == 0:
                ans += 1
            k += 1
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate quickly recognize the mathematical pattern behind consecutive sums?
question_mark
Does the candidate efficiently handle large inputs (up to 10^9)?
question_mark
Is the candidate able to optimize the solution by reducing unnecessary checks or calculations?

warning

常见陷阱

外企场景

error
Forgetting that the starting number must be positive, which could lead to invalid sequences.
error
Misunderstanding the sum formula for consecutive integers, leading to incorrect solutions.
error
Not optimizing the solution by stopping once k exceeds sqrt(n), resulting in inefficient solutions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Can this problem be generalized to find all sequences for a range of numbers?
arrow_right_alt
How would the approach change if negative integers were allowed?
arrow_right_alt
What if the sequence must include at least three integers instead of two?

help

常见问题

外企场景

继续练习

#869 重新排序得到 2 的幂 #906 超级回文数 #970 强整数