Is Consecutive Numbers Sum easy or hard?

The problem is labeled Hard because the key insight is mathematical rather than algorithmic. Without recognizing the arithmetic series formula, most solutions attempt brute-force enumeration. Once the formula is derived, the implementation becomes short and efficient.

Consecutive Numbers Sum Python/Java solution

In Python or Java, implement a loop over sequence length k and compute (n - k*(k-1)/2). If the result is positive and divisible by k, increment the answer. This implementation runs in O(sqrt(n)) time and works efficiently even for large inputs.

How to solve Consecutive Numbers Sum in O(n)?

A straightforward enumeration can iterate starting numbers and keep adding consecutive integers until the sum reaches or exceeds n. This brute-force idea runs in roughly O(n) or worse depending on the implementation. Optimizing with the arithmetic series formula reduces the complexity further to O(sqrt(n)).

What is the best approach for Consecutive Numbers Sum?

The optimal approach uses a mathematical observation about arithmetic sequences. A sequence of length k starting at x sums to k*x + k*(k-1)/2. By iterating possible lengths k and checking if (n - k*(k-1)/2) is divisible by k, you can determine valid sequences in O(sqrt(n)) time with O(1) space.

Is Consecutive Numbers Sum asked at Google/Amazon/Meta?

Consecutive Numbers Sum is a classic number theory and enumeration problem similar to questions asked in Google and Amazon interviews. It tests whether you can translate a sequence problem into a mathematical formula and reduce brute-force search using algebra.

What data structure is used in Consecutive Numbers Sum?

The optimal solution does not require complex data structures. It relies on arithmetic formulas and integer checks. Alternative recursive implementations may use memoization with a hash map or dictionary to cache intermediate states.

What is the time complexity of Consecutive Numbers Sum?

The optimal mathematical solution runs in O(sqrt(n)) time because the sequence length k only needs to be tested up to roughly sqrt(2n). Space complexity is O(1) since the algorithm only keeps a few variables while checking divisibility conditions.

Description Solution Video 9:50

829. Consecutive Numbers Sum

Hard43.2% acceptance7 companies

Given an integer n, return the number of ways you can write n as the sum of consecutive positive integers.

Example 1:

Input: n = 5
Output: 2
Explanation: 5 = 2 + 3

Example 2:

Input: n = 9
Output: 3
Explanation: 9 = 4 + 5 = 2 + 3 + 4

Example 3:

Input: n = 15
Output: 4
Explanation: 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5

Constraints:

1 <= n <= 10⁹

Asked at 7 companies

D. E. Shaw Microsoft Oracle Zoho Airbnb Tiktok

Google

Topics

Enumeration Math

9:50

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def consecutiveNumbersSum(self, n: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

Your code is saved on this device.Solution