Katkat
Back

Count Consecutive Positive Integer Sums

AirbnbSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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

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.