Approach #1: Brute Force [Time Limit Exceeded]
Intuition and Algorithm
For each starting number, we scan forward until we meet or exceed the target N
. If we meet it, then it represents one way to write N
as a sum of consecutive numbers.
For example, if N = 6
, and we scan forward from 1
, we'll get 1 + 2 + 3 = 6
which contributes to the answer. If we scan forward from 2
, we'll get 2 + 3 + 4
(the first time that the sum is >= N
) which is too big.
Complexity Analysis

Time Complexity: .

Space Complexity: .
Approach #2: Mathematical (Naive) [Time Limit Exceeded]
Intuition and Algorithm
We can model the situation by the equation . Here, . Using the identity , we can simplify this equation to .
From here, clearly . We can try every such . We need to be a nonnegative integer for a solution to exist for the we are trying.
Complexity Analysis

Time Complexity: .

Space Complexity: .
Approach #3: Mathematical (Fast) [Accepted]
Intuition and Algorithm
As in Approach #2, with . Call the first factor, and the second factor. We are looking for ways to solve this equation without trying all possibilities.
Now notice that the parity of and are different. That is, if is even then the other quantity is odd, and vice versa. Also, , so the second factor must be bigger.
Now write where is odd. If we factor , then two candidate solutions are , or . However, only one of these solutions will have the second factor larger than the first. (Because , we are guaranteed that one factor is strictly larger.)
Thus, the answer is the number of ways to factor the odd part of .
Complexity Analysis

Time Complexity: .

Space Complexity: .
Analysis written by: @awice.