Project Euler Problem 4 Solution

First posted on 09/09/2012

Question

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.

Solution

import java.util.ArrayList;
import java.util.Collections;

public class Palindrome2 {
	public static void main(String[] args){
		long begin = System.currentTimeMillis(); // Start beginning compile time
		int prod = 0;
		ArrayList<Integer> max = new ArrayList<Integer>(); // Arrays of largest palindrome
		
		for(int i = 100; i <= 999; i++){
			for(int j = 100; j <= 999; j++){
				prod = i*j;
				
				if(isPalindrome(prod))
					max.add(prod); // Adds largest palindrome found in the array
			}
		}
		// Sorts the array
		// Won't get accurate answer if not sorted
		// Because second parent increment; 101*100 number gets lowered and so forth
		Collections.sort(max);
		
		// There are same values in the array
		// Because 101*102 is the same as 102*101
		System.out.println(max);
		
		long end = System.currentTimeMillis(); // Stops the compiling time
		System.out.println(end-begin + " ms"); // Output total time compiled
	}

	private static boolean isPalindrome(int prod) {
		String strProd = "" + prod; // Converts int prod to String
		int leftChar = 0; // Leftmost character
		int rightChar = strProd.length() -1; // Rightmost character
		
		
		while(leftChar < rightChar){
			if(strProd.charAt(leftChar) != strProd.charAt(rightChar))
				return false;
			
			leftChar++;
			rightChar--;
		}
		
		return true;
	}
}

Answer: 906609

Footnote

Palindrome algorithm taken from Leepoint's Java notes.

Alternative solution

for(int i = 100; i <= 999; i++){
 for(int j = 100; j <= 999; j++){
  prod = i*j;
    
  if(isPalindrome(prod) && prod > max)
   max = prod;
 }
}

System.out.println(max); 

Where in the second for loop, if product of i*j exceeds the latest found palindrome, it will be replaced by a new value of palindrome

Show Comments

Get the latest posts delivered right to your inbox.