Consecutive numbers sum

Math Enumeration

42.6% acceptance

Feb 22, 2026

1451

1394

Given an integer n, return the number of ways you can write n as the sum of consecutive positive integers.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

/*
 * Given an integer n, return the number of ways you can write n as the sum of consecutive positive integers.
 * 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 <= 109
 */

impl Solution {
  pub fn consecutive_numbers_sum(n: i32) -> i32 {
    // k consecutive from m: k*m + k*(k-1)/2 = n
    // m = (n - k*(k-1)/2) / k must be >= 1 and integer
    let mut ans = 0;
    let mut k = 1i32;
    loop {
      let sum = k * (k - 1) / 2;
      if sum >= n { break; }
      let rem = n - sum;
      if rem % k == 0 {
        ans += 1;
      }
      k += 1;
    }
    ans
  }
}