Project Euler: Problem 4 (in Groovy)

Problem 4 in Project Euler is as follows:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

I found this problem significantly easier than problem 3, thankfully.

My first step was to write a helper method:

	boolean isPalindrome(int num)

My first attempt was, as usual, the brute force approach. Namely, go through every number from 100 to 999 and for each, multiply it by every number between 100 and 999. Check if the result of each of the roughly one million calculations is a palindrome – and store it if it is the biggest one yet.

My next approach was better and involved starting from the top (999 to 100) instead of the other way round. This means we can check if the largest palindrome we could possible find is smaller than what we have already found, thereby avoiding a large number of useless calculations.

This gave me a solution that runs in approx 500ms on my local PC.

Here is my final solution:

int largestPalindrome = 0;
for (i in 999..100) {			
	if ( (i*i) < largestPalindrome) {
		//the largest possible number we can now find (i*i) 
		//is smaller than the biggest palindrome already found
		break;
	}
	for (j in i..100) {
		int candidate = i*j;
		if ( candidate < largestPalindrome) {
			//largest number we can now find in this inner loop
			//is smaller than the biggest palindrome already found
			break;
		}
		if (isPalindrome(candidate)) {
			if (candidate>largestPalindrome) {
				largestPalindrome = candidate;
				break;//no point checking smaller numbers of j
			}
		} 
	}
}
println("largestPalindrome);

And finally, my isPalindrome method:

public static boolean isPalindrome(Integer num) {
	boolean isPalindrome=true;
	char[] numChars = num.toString().toCharArray();
	int endPoint = numChars.length() - 1;
	int midPoint = numChars.length() / 2;
	for (i in 0..midPoint) {
		char a = numChars[i];
		char b = numChars[endPoint-i];
		if (a != b) {
			isPalindrome=false;
			break;
		}
	}
	return isPalindrome;
}

Tags: euler, groovy