829. Consecutive Numbers Sum

Time: O(√n)

Space: O(1)

Approach

For each k, check if (n - k(k-1)/2) is positive and divisible by k; count valid partitions.

Key Techniques

Math problems test number theory, combinatorics, and modular arithmetic. Common tools: GCD/LCM (Euclidean algorithm), prime sieve, modular inverse (Fermat's little theorem), digit manipulation, and bit tricks. Overflow is a key concern in C# — use long when products may exceed 2³¹.

829.cs

// Approach: For each k, check if (n - k(k-1)/2) is positive and divisible by k; count valid partitions.
// Time: O(√n) Space: O(1)

public class Solution
{
    public int ConsecutiveNumbersSum(int n)
    {
        int ans = 0;
        for (int i = 1, triangleNum = i; triangleNum <= n; ++i, triangleNum += i)
            if ((n - triangleNum) % i == 0)
                ++ans;
        return ans;
    }
}

Was this solution helpful?