Coding questions · Airbnb

Count Consecutive Positive Integer Sums

Count representations of a positive integer as one or more consecutive positive integers, including the one-term representation. Derive the arithmetic condition for each sequence length and use a square-root bound rather than testing every possible starting value.

Given a positive integer n, return the number of ways to write n as a sum of one or more consecutive positive integers.

Two representations are different if they have different starting values or lengths. The one-term representation n itself counts.

Function Signature

def count_consecutive_sums(n: int) -> int:

Examples

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

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

Constraints

1 <= n <= 10^12
Every term in a representation must be a positive integer.
Return an integer count; do not return the representations themselves.

Clarifications

Terms must increase by exactly one.
Order is fixed by consecutiveness, so reversing a sequence is not another representation.

Hints

For a chosen sequence length, express the sum using its first value.
Use arithmetic bounds to avoid checking all possible starting values.

Count Consecutive Positive Integer Sums

Hints

The answer equals the number of odd divisors of n.
Remove factors of two before factoring the odd part.
For a prime exponent e, multiply the divisor count by e + 1.

Approach

Positive consecutive-sum representations are in bijection with odd divisors of n. Remove powers of two, factor the odd part, and compute its divisor count from its prime exponents.

Time complexity: O(sqrt(n)) in the worst case.
Space complexity: O(1).