Consecutive Numbers Sum

Given an integer n, return the number of ways you can write n as the sum of consecutive positive integers. Let's break this down with examples:

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^9

Can you provide an efficient algorithm to solve this problem and explain its time and space complexity?

def consecutive_numbers_sum(n: int) -> int:
    """Given an integer n, return the number of ways you can write n as the sum of consecutive positive integers."""
    count = 0
    for k in range(1, int((2 * n)**0.5) + 1):
        if (n - (k * (k - 1) // 2)) > 0 and (n - (k * (k - 1) // 2)) % k == 0:
            count += 1
    return count

# Example usage
n = 5
result = consecutive_numbers_sum(n)
print(f"The number of ways to write {n} as the sum of consecutive positive integers is: {result}")

n = 9
result = consecutive_numbers_sum(n)
print(f"The number of ways to write {n} as the sum of consecutive positive integers is: {result}")

n = 15
result = consecutive_numbers_sum(n)
print(f"The number of ways to write {n} as the sum of consecutive positive integers is: {result}")

Explanation:

The problem asks us to find the number of ways to express a given integer n as a sum of consecutive positive integers.

The key idea is to iterate through possible lengths k of the consecutive sequence and check if such a sequence exists.

Let's say we want to express n as a sum of k consecutive integers starting from x. Then:

n = x + (x + 1) + (x + 2) + ... + (x + k - 1)

n = k * x + (1 + 2 + ... + k - 1)

n = k * x + k * (k - 1) / 2

k * x = n - k * (k - 1) / 2

x = (n - k * (k - 1) / 2) / k

For x to be a positive integer, (n - k * (k - 1) / 2) must be greater than 0 and divisible by k.

So, we iterate through possible values of k and check these conditions. The upper bound for k can be derived from the condition that x must be positive:

n - k * (k - 1) / 2 > 0

n > k * (k - 1) / 2

2 * n > k * (k - 1)

2 * n > k^2 - k

Since k^2 - k is approximately k^2 for larger k, we can say k is roughly bounded by sqrt(2 * n). This gives us the range for iteration.

Big(O) Run-time Analysis:

The outer for loop iterates up to sqrt(2*n), so the time complexity is O(sqrt(n)). Inside the loop, we perform constant-time arithmetic operations. Therefore, the overall time complexity is O(sqrt(n)).

Big(O) Space Usage Analysis:

The space complexity is O(1) because we only use a few integer variables (count, k, n) regardless of the input value. We are not using any extra data structures that scale with the input.