0829 - Consecutive Numbers Sum (Hard)

Problem Link

https://leetcode.com/problems/consecutive-numbers-sum/

Problem Statement

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 <= 10^9

Approach: Math

The first observation is that $n$itself is one of the answer. We can define $ans = 1$.

Let $x$ be the first number of the sequence, then we should have

$$n = x + (x + 1) + (x + 2) + ... + (x + (k - 1))$$

We can arrange the formula. First there are $k$ terms of $x$ so we can just multiply them together. The remaining sum is just $0 + 1 + 2 + ... + (k - 1)$ which is $k * (k - 1) / 2$. Why? We can get that from sum of $n$ terms in Arithmetic Progress (A.P.) formula

$$S = (n / 2) * (2 * a + (n - 1) * d)$$

where $a$is the first term and $d$ is the common difference.

We can further transform from

$$S = (n / 2) * (a + a + (n - 1) * d)$$

to the following expression

$$S = (n / 2) * (a * l)$$

where $l$is the last term and it is equivalent to $a + (n - 1) * d$.

Back to our problem, from $0 + 1 + 2 + ... + (k - 1)$, we can see that the first term is 0 and and last term is $(k - 1)$. Therefore, we can know that $0 + 1 + 2 + ... + (k - 1) = (k / 2) * (0 + (k - 1)) = k * (k - 1) / 2$.

Now we have $k * x = n - k * (k - 1) / 2$, which means we can construct a sum of $n$using $k$terms starting from $x$ if $n - k * (k - 1) / 2$ is a multiple of $k$. We can iterate $k$and check if this statement is true or not. The next problem would be "What is the range of $k$?".

Since $n$itself is already considered, so we need to start $k$ from 2. From the above formula, $n - k * (k - 1) / 2$ needs to be greater than 0.

$$n - k * (k - 1) / 2 > 0$$ $$k * (k - 1) < 2 * n$$

The upper bound for $k$ approximately would be around $\sqrt {2 * n + k}$. Therefore, we iterate $k$ from $2$ to $\sqrt {2 * n + k}$ to check if $n - k * (k - 1) / 2$ is a multiple of $k$. If so, it means we have one sequence so we increase the answer by $1$.

Written by @wingkwong

class Solution {
public:
    int consecutiveNumbersSum(int n) {
        int ans = 1;
        // n = x + (x + 1) + (x + 2) + ... + (x + (k - 1))
        // n = k * x + k * (k - 1) / 2
        // k * x = n - k * (k - 1) / 2
        // n - k * (k - 1) / 2 > 0
        // k * (k - 1) < 2 * n
        // ~= k * k < 2 * n + k
        for (int k = 2; k < sqrt(2 * n + k); k++) {
            ans += (n - (k * (k - 1) / 2)) % k == 0;
        }
        return ans;
    }
};