Skip to content
August 15, 2011 / oop123

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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: