Optimizing "Herd Sums" problem using dynamic programming

Question

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<Integer,Integer> cache = new HashMap<>(); static { cache.put(0, 0); } public static void main(String[] args) { long start = System.nanoTime(); String[] in = getInput(); int inRead = 0; while (inRead < in.length) { int numCows = Integer.parseInt(in[inRead++]); System.out.println(getNumSums(numCows)); } long end = System.nanoTime(); long elapsed = (end - start)/1000000000; System.out.println("Elapsed:" + elapsed); } private static int getNumSums(int numCows) { int count = 0; for (int i = 1; i <= numCows; i++) { int sum = sumTo(i); if (sum >= numCows) { int j = 1; while (sum > numCows) { sum -= j++; } if (sum == numCows) ++count; } } return count; } private static int sumTo(int end) { if (cache.get(end) == null) { int prev = cache.get(end - 1); cache.put(end, prev + end); } return cache.get(end); } private static String[] getInput() { List<String> ret = new ArrayList<>(); String line; try (BufferedReader br = new BufferedReader(new FileReader("g_input.txt"))){ while(!(line = br.readLine()).equals("-1")) { ret.add(line); } } catch (IOException e) { // TODO Auto-generated catch block e.printStackTrace(); } return ret.toArray(new String[ret.size()]); } } 

Input

1 2 3 4 5 10 15 99 200 578 690 30007 45000 143929 9909909 10000000 -1 

Output

1 1 2 1 2 2 4 6 3 3 8 4 15 4 24 8 

Problem

private static int getNumSums(int numCows) { int count = 0; for (int i = 1; i <= numCows; i++) { int sum = sumTo(i); if (sum >= numCows) { int j = 1; while (sum > numCows) { //this is slow sum -= j++; } if (sum == numCows) ++count; } } return count; } 

This part seems to be the slow one. I've make the sumTo() dynamic but I can't think of a way to make this part dynamic.

It works alright until it reaches numCows = 9909909, when it reaches that part it just becomes really slow.

Answer 1

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.

Answer 2

Use maths. Rewrite your getNumSum method like this (you don't need your sumTo and cache):

private static int getNumSums(int numCows) { int limit = (int)Math.sqrt(2 * numCows); int count = 0; for (int m = 1; m <= limit; ++m) { if ((2 * numCows + m * (m + 1)) % (2 * m) == 0) { ++count; } } return count; } 

See this question and the accepted answer for an explanation of how this works.

Answer 3

A group of consecutive integers adds up to N.

The number of integers in that group is odd or even.

You may have n integers, n odd. If the middle one is k, then the sum is n*k. You may have 2n integers. If the two in the middle are k and k+1, then the sum is n*(2k + 1).

So the answer is quite closely related to finding all ways to write N as the product of two integers, which is very easily done by trial division with divisors <= sqrt (N). Let N = a*b. If a is odd then we could have n = a integers from b - (a-1)/2 to b + (a-1)/2. If b is odd then we could have n = 2a integers from (b + 1)/2 - a to (b - 1)/2 + a. (You better check this).