Consecutive Numbers Sum
Asked at Microsoft
Problem
Given a positive integer n, return the number of ways to write n as a sum of two or more consecutive positive integers. For example, n=9 can be written as 9, 4+5, 2+3+4, so the answer is 3.
Asked At
| Company | Difficulty | |
|---|---|---|
| Microsoft | Hard | View all Microsoft questions → |
How to Think About It
Brute force: for every starting number a and every length k, check if a + (a+1) + ... + (a+k-1) == n. The sum is k*a + k(k-1)/2. This is O(sqrt(n)^2) = O(n) which is too slow.
Key insight: the sum of k consecutive numbers starting at a is k*a + k(k-1)/2 = n. Rearranging: a = (n - k(k-1)/2) / k. For a valid solution, a must be a positive integer, meaning n - k(k-1)/2 must be divisible by k and the result must be > 0.
Bound on k: since a >= 1, we need k(k+1)/2 <= n, so k <= sqrt(2n). This means we only need to try k from 1 to sqrt(2n), giving O(sqrt(n)) time.
Visual walkthrough for n=9: k=1: a=9 (valid). k=2: a=(9-1)/2=4 (valid, 4+5=9). k=3: a=(9-3)/3=2 (valid, 2+3+4=9). k=4: a=(9-6)/4=0.75 (invalid). k>4: k(k+1)/2 > 9. Answer: 3.
The count of ways equals the count of odd divisors of n. This is because n = k*a + k(k-1)/2 simplifies to 2n = k(2a+k-1), where k and (2a+k-1) have opposite parity. Each valid factorization of 2n into k and (2a+k-1) with k >= 1 gives a solution.
Edge cases: n=1 returns 1 (just [1]). n=2 returns 1 (just [2]). Large n up to 10^9 still works in O(sqrt(n)).
Optimal Approach
Step 1: Initialize count = 0.
Step 2: For k from 1 while k*(k+1)/2 <= n:
- Compute remainder = n - k*(k-1)/2
- If remainder > 0 and remainder % k == 0: count += 1
Step 3: Return count.
Walkthrough with n=9:
- k=1: remainder = 9-0 = 9. 9%1==0. Count=1.
- k=2: remainder = 9-1 = 8. 8%2==0. Count=2.
- k=3: remainder = 9-3 = 6. 6%3==0. Count=3.
- k=4: remainder = 9-6 = 3. 3%4!=0.
- k=5: 5*6/2=15 > 9. Stop.
- Return 3.
Time: O(sqrt(n)). Space: O(1).
What Trips People Up in Real Interviews
Trying to enumerate all possible starting numbers and lengths. The key is to fix k (length) and compute a directly.
Forgetting that a must be a positive integer (a >= 1). If the formula gives a <= 0 or a is not an integer, skip that k.
Off-by-one in the bound. Use k*(k+1)//2 <= n as the loop condition. Going one k too far wastes time but does not give wrong answers.
Confusing this with counting subsequences. This is about consecutive POSITIVE integers (not subsequences), and the order is fixed.
Not handling n=1 correctly. n=1 has exactly one representation: [1]. The formula gives k=1, a=1 which is valid.
Solution Code
def consecutiveNumbersSum(n):
count = 0
k = 1
while k * (k + 1) // 2 <= n:
rem = n - k * (k - 1) // 2
if rem > 0 and rem % k == 0:
count += 1
k += 1
return countFrequently Asked Questions
What is the Consecutive Numbers Sum problem?
Given a positive integer n, return the number of ways to write n as a sum of two or more consecutive positive integers. For example, n=9 can be written as 9, 4+5, 2+3+4, so the answer is 3.
How do you solve Consecutive Numbers Sum?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Consecutive Numbers Sum?
Consecutive Numbers Sum is asked at Microsoft. It is a hard difficulty problem.
What are common mistakes on Consecutive Numbers Sum?
- Trying to enumerate all possible starting numbers and lengths. The key is to fix k (length) and compute a directly.
- Forgetting that a must be a positive integer (a >= 1). If the formula gives a <= 0 or a is not an integer, skip that k.
- Off-by-one in the bound. Use `k*(k+1)//2 <= n` as the loop condition. Going one k too far wastes time but does not give wrong answers.
- Confusing this with counting subsequences. This is about consecutive POSITIVE integers (not subsequences), and the order is fixed.
- Not handling n=1 correctly. n=1 has exactly one representation: [1]. The formula gives k=1, a=1 which is valid.