Optimizing "Herd Sums" problem using dynamic programming

I'm trying to solve a practice problem and all is well except for the last 2 inputs my solution is too slow. Just one loop is slowing it down I think.

Herd Sums


Execution Time Limit: 2 seconds



Problem Statement


The cows if farmer John's herd are numbered and banded with consecutive integers from 1 to N (1 ≤ N ≤ 10,000,000). When the cows come to the barn for milking, they always come in sequential order from 1 to N.


Farmer John, who majored in mathematics in college and loves numbers, often looks for patterns. He has noticed that when he has exactly 15 cows in his herd, there are precisely four ways that the numbers on any set of one or more consecutive cows can add up to 15 (the same as the total number of cows). They are: 15, 7 + 8, 4 + 5 + 6, and 1 + 2 + 3 + 4 + 5.


When the number of cows in the herd is 10, the number of ways he can sum consecutive cows and get 10 drops to two: namely 1 + 2 + 3 + 4 and 10.


Write a program that will compute the number of ways farmer John can sum the numbers on consecutive cows to equal N.

Input


The input consists of several test cases, each on a separate line. Each test case consists of a single integer N. The program should terminate when it encounters -1. This should not be processed.

Output


For each test case, output the number of ways Farmer John can sum the numbers on consecutive cows to equal N. Print the output for each test case in a separate line.

Sample Input

15
10
-1

Sample Output

4
2

Full Solution

```
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {
static Map cache = new HashMap<>();
static {
cache.put(0, 0);
}
public static void main(String[] args) {
long start = System.nanoTime();
String[] in = getInput();
int i

There are some other Java gurus around here who might know some Java-specific tips and tricks, but... I want to look at something else you're doing in the algorithm.

First of all, we know from the problem statement that any positive integer will have at least 1 possible answer, that is, itself.

What we can also know from basic math knowledge is that the largest starting number is going to be just below half of the total number.

For example, with 100, the largest possible starting number would be 49, because 49+50 is less than 100, but 50+51 is more than 100. 49+50 isn't one of the solutions, but it does represent something important to us: the largest possible starting number. This is where we can stop checking numbers.

We can extend this thinking further. For example, a number that is evenly divisible by 3 will have a solution by starting with the largest number that is less than 1/3rd the number and taking the two following numbers. For example, 1/3rd of 3 is 1. The largest number under this is 0. 0+1+2 = 3. A better example is 6. One third of 6 is 2. The largest number under this is 1. 1+2+3 = 6. This will be exactly true for every multiple of 3.

30: 1/3 = 10. One less than 10 is 9. 9+10+11 = 30.

But there's something more to learn from this...

• If \$n_1 + n_2 = N\$, and \$(n_1, n_2)\$ are consecutive, then \$N\$ is of the form \$2n_1 + 1\$.

-
If \$n_1 + n_2 + n_3 = N\$, and \$(n_1, n_2, n_3)\$ are consecutive, then \$N\$ is of the form \$3n_2\$.

Think of the sum as \$(n_2 - 1) + n_2 + (n_2 + 1)\$.

-
If \$n_1 + n_2 + n_3 + n_4 = N\$, and \$(n_1 \ldots n_4)\$ are consecutive, then \$N\$ is of the form \$4n_2 + 2\$.

-
If \$n_1 + n_2 + n_3 + n_4 + n_5 = N\$, and \$(n_1 \ldots n_5)\$ are consecutive, then \$N\$ is of the form \$5n_3\$.

Think of the sum as \$(n_3 \underbrace{- 2) + (n_3 \underbrace{- 1) + n_3 + (n_3 +} 1) + (n_3 +} 2)\$.

For any run length \$L\$, there's at most one run of \$L\$ consecutive numbers that can sum to \$N\$. This is true for any run of positive, consecutive integers. Moreover, each run of length \$L\$ will be centered at \$\frac{N}{L}\$.

The point is, the solution should be mostly formulaic. The only searching you need to do is to check whether \$N\$ is of the form \$k,\ 2k + 1,\ 3k,\ 4k + 2,\ 5k,\ 6k + 3, \ldots\$. You should be able to accomplish that in \$\mathrm{O}(N)\$ time.

StackExchange Code Review Q#48640, answer score: 13