Skip to content
April 3, 2011 / oop123

Project Euler #87 – Java

You can see the problem here: Problem #87.

I just chose an easy problem to do because I have no idea how to do the other problems. Well, at least I can’t think of a solution within one minute of reading it. I’m lazy that way. This problem is easy enough. I already created a class representing prime sieve, and all you need to do is create combinations of prime squares, cubes, and fourth powers and keep track those with sums below 50,000,000. The tricky (although NOT that tricky) part of the question is to realize there are ways to reach the same sum with different combinations, so I just made a HashSet to catch the duplicate sums.

int LIMIT = 50000000;
int[] primes = new EratosthenesSieve(10000).toArray();
LinkedList<Integer> squares = new LinkedList<Integer>(),
LinkedList<Integer> cubes = new LinkedList<Integer>(),
LinkedList<Integer> fours = new LinkedList<Integer>();

//fill the LinkedLists with the prime squares, cubes, and fourth powers
int temp = 4, count = 0;
while (temp < LIMIT) {
	squares.add(temp);
	temp = primes[++count] * primes[count];
}
temp = 8; count = 0;
while (temp < LIMIT) {
	cubes.add(temp);
	temp = primes[++count] * squares.get(count);
}
temp = 16; count = 0;
while (temp < LIMIT) {
	fours.add(temp);
	temp = primes[++count] * cubes.get(count);
}

HashSet<Integer> noDups = new HashSet<Integer>();
for (Integer square : squares) {
	for (Integer cube : cubes) {
		for (Integer four : fours) {
			temp = square + cube + four;
			if (temp > LIMIT) {
				break;
			} else {
				noDups.add(temp);
			}
		}
	}
}
System.out.println(noDups.size());

Runs in about 1.7 seconds on my computer.

This seems slow for what it’s doing, so I decided to optimize it a little. Instead of using a HashSet, I decided to put all the numbers inside an array, and after getting all the sums, sort it and remove the duplicates (they will be adjacent to each other), and count the number of remaining elements. Surprisingly, the sort and remove method actually run faster than HashSet. This is what I came up with (I wrote an ArraysUtils class containing all the removeDuplicates stuff):

int LIMIT = 50000000;
int[] primes = new EratosthenesSieve(10000).toArray();
LinkedList<Integer> squares = new LinkedList<Integer>(),
LinkedList<Integer> cubes = new LinkedList<Integer>(),
LinkedList<Integer> fours = new LinkedList<Integer>();

//fill the LinkedLists with the prime squares, cubes, and fourth powers
int temp = 4, count = 0;
while (temp < LIMIT) {
	squares.add(temp);
	temp = primes[++count] * primes[count];
}
temp = 8; count = 0;
while (temp < LIMIT) {
	cubes.add(temp);
	//save a multiplication, not sure if it helps though, with the unboxing and method overhead
	temp = primes[++count] * squares.get(count);
}
temp = 16; count = 0;
while (temp < LIMIT) {
	fours.add(temp);
	//save two multiplications, not sure if it helps though, with the unboxing and method overhead
	temp = primes[++count] * cubes.get(count);
}

//hard coded so the array can hold enough sums, in real life I progressively increase the size until it fits
int[] sums = new int[1200000];
count = -1;
for (Integer square : squares) {
	for (Integer cube : cubes) {
		for (Integer four : fours) {
			temp = square + cube + four;
			if (temp > LIMIT) {
				break;
			} else {
				sums[++count] = temp;
			}
		}
	}
}
ArraysUtils.sortAndRemoveDuplicates(sums);
System.out.println(sums.length);

Runs about ^400 milliseconds on my computer now. Note that more autoboxing in the first code so that needs to be taking into account, but apparently if you don’t care about the order of the elements, sorting an array and then remove the (adjacent) duplicate elements are way faster than a HashSet, interesting…

80 questions complete now, 20 more to go. It’s probably going to take me half a year though, sigh. 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: