# Project Euler #88 – Java

You can see the problem here: Problem #88.

This problem is easier than it looks. As you can see from the question, we can add 1s to a list of factor to change its sum but keep its product the same. For example, (2 * 3) = 6, but 2 + 3 only equals 5. We can add 1 to the list of factors [(2 * 3) -> (1 * 2 * 3)] which changes the list’s sum to 6 but keeps its product at 6. Using this observation, we can derive a simple formula that can calculate the *k* for any list of factors:

**k = number_of_factors – sum_of_factors + product_of_factors**

So let’s say the list of factors is (2 * 3 * 4), the product_of_factors would be 24, the number_of_factors would be 3, and the sum_of_factors would be 9. Plug those into the above formula, and we get k = 18.

To solve this question, I used a dynamic programming approach again in which I used an array to accumulate all the lists of factors. However, why calculate the lists of factors when we can just keep track of their sum_of_factors and number_of_factors? After I finished the question, I realized the number_of_factors and sum_of_factors can be combined into a single number to be keep track of (number_of_factors – sum_of_factors, see the formula for *k*), leading to the following (messy) code.

final int SIZE = 12000; final int RANGE = 24000; //P.S. RANGE can be smaller, down to 12,200 int[] k = new int[SIZE + 1]; List<Set<Integer>> nums = new ArrayList<Set<Integer>>(RANGE + 1); for (int i = 0; i <= RANGE; i++) nums.add(new HashSet<Integer>()); //dynamically calculate all the k's for (int i = 2; i <= RANGE / 2; i++) { nums.get(i).add(-i + 1); for (int num : nums.get(i)) { int current = i + i; int new_num = num - 1; for (int j = 2; j <= i && current <= RANGE; j++) { nums.get(current).add(new_num); int pk = current + new_num; if (pk <= SIZE && (current < k[pk] || k[pk] == 0)) k[pk] = current; new_num--; current += i; } } } //show the answer boolean success = true; for (int i = 2; i < k.length; i++) if (k[i] == 0) success = false; if (success) { k = ArraysUtils.sortAndRemoveDuplicates(k); int sum = 0; for (int i : k) sum += i; System.out.println(sum); }

Runs in around 500 milliseconds on my computer (200 milliseconds if RANGE = 13000). CU

## Leave a Reply