Count Consecutive Positive Integer Sums
Company: Airbnb
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
# Count Consecutive Positive Integer Sums
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
```python
def count_consecutive_sums(n: int) -> int:
```
### Examples
```text
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.
Overview: 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.
Return the number of representations of a positive integer as one or more consecutive positive integers. The one-term representation counts, and only the count—not the sequences—is returned.
Constraints
- n is a positive integer no greater than 10^12.
- Every term must be positive.
- Terms increase by exactly one.
- Different starts or lengths are distinct.
- Return an exact integer count.
Examples
Input: (1,)
Expected Output: 1
Explanation: One is represented only by itself.
Input: (2,)
Expected Output: 1
Explanation: Two has only its one-term representation.
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.