Consecutive Numbers - Leetcode Solution

Problem Statement:

Given an integer n, return all the positive integers less than or equal to n that can be represented as a sum of consecutive positive integers.

Example:

Input: 5 Output: [2,3] Explanation: 2 = 1 + 1, 3 = 1 + 2

Input: 15 Output: [1,2,4,7] Explanation: 1 = 1, 2 = 2, 4 = 1 + 3, 7 = 1 + 2 + 4

Approach:

One of the most intuitive solutions to this problem is to iterate over all possible starting points of consecutive integers and calculating the sum until it is greater than n. If it becomes equal to n we can append it to the answer list. Otherwise, we continue with the next starting point.

Code:

Here's the implementation of the above approach in Python:

class Solution:
    def consecutiveNumbersSum(self, n: int) -> List[int]:
        # initialize starting point
        start = 1
        
        # initialize answer array
        ans = []
        
        while start * (start + 1) // 2 <= n:
            # initialize sum and counter
            s, k = 0, start
            
            while s < n:
                # calculate sum of consecutive integers
                s += k
                k += 1
                
                # if the sum is equal to n, append it to answer array
                if s == n:
                    ans.append(start)
                    break
                    
        # increment starting point
            start += 1
            
        return ans

Complexity Analysis:

Time Complexity: O(n^2)

The time complexity of the above approach is O(n^2) because we are iterating over all possible starting points of consecutive integers and calculating the sum of each sequence until it either becomes greater than n or equal to n.

Space Complexity: O(1)

The space complexity of the above approach is O(1) because we are only using constant space for storing the answer array and other variables.

1