Thread: Efficiency problem

I have the following problem to solve:

Find the largest palindromic number made from the product of two N-digit numbers.


This is my class to find the largest palindromic number:

 
public class LargestPalindromeNumber {
 
	private long factorLength, highValue, max = 0, factor1 = 0, factor2 = 0;
 
	public LargestPalindromeNumber(long n){
 
		factorLength = n; // number of digits in each factor
		highValue = (long) (Math.pow(10, factorLength) - 1); // highest value a factor can have
 
	}
 
 
 
 
	public long getLargestPalindrome1(){
 
		for( long i = highValue; i > highValue/10 ; i = i - 1){
 
			if(i  < factor2) return max;
 
			for(long j = i ; j > highValue / 10; j = j - 1 ){
 
				if(i % 11 == 0 || j % 11 == 0){
 
					if(i*j < max) j = highValue/10;
 
 
					else{ 
 
						if(isPalindrome(i * j)){
						max = i * j;
						factor1 = i;
						factor2 = j;
						j = highValue/10;
 
					}
					}
				}
			}// end second for loop
 
		}// end first for loop
 
		return max;
 
	}// end getLargestPalindrome()
 
 
	// Checks whether a number is a palindrome 
	public boolean isPalindrome(long n){
 
		long reverse = 0;
		long value = n;
 
		while(n > 0){
 
			reverse = (reverse * 10) + (n % 10);
 
			n = n / 10;
 
		}// end while
 
		return(value == reverse);
 
	}// end isPalindrome
 
 
	// Returns the value of factor1
	public long getFactor1(){
		return factor1;
	}
 
 
	// Returns the value of factor2
	public long getFactor2(){
		return factor2;
	}
 
 
}// end LargestPalindromeNumber class

This is my main class:

 
import tcdIO.*;
 
public class Main {
 
 
	public static void main(String[] args) {
 
		Terminal window;
		LargestPalindromeNumber bigPal;
		long ndigit;
 
		window = new Terminal("Find the Largest Palindromic Number");
 
		window.println("This program finds the largest palindromic number that is a product of two N-Digit numbers.\n");
		window.println();
 
		ndigit = window.readInt("Enter the number of digits in the factors : ");
		bigPal = new LargestPalindromeNumber(ndigit);
 
 
		window.println();
		window.println("The largest palindromic number that is a ");
		window.println("product of two " + ndigit + " digit numbers is: "); 
		window.println();
		window.println( "" + bigPal.getLargestPalindrome1() );
		window.println();
		window.println("whose factors are : " + bigPal.getFactor1() + " and " + bigPal.getFactor2() + ".");
 
	}// end main()
 
}// end Main class

Q: Can you suggest ways to improve the efficiency of this code as it takes a long time to get an answer when i enter 9-digit by 9-digit factors, in fact I haven't waited for it to produce an answer yet.

Note:
1) The palindromic numbers I am searching for will be divisible by 11.
2) It works fine up until 8-digit by 8-digit numbers.

I have tried that already but its complicated because if the factors are even number digits e.g. 99, I have to decrease i by 11 and j by 1, but if it is an odd number of digits e.g. 999 I have to decrease i by 1 and j by 11. Which sounds simple to implement but it is difficult to insure every possible combination of i * j is checked.

I'll try again though.

Edit: Also I let my program run until it found the 9-digit * 9-digit largest palindrome. It took 5/6 minutes and I am fairly sure I cannot compute any palindromes for n-digit factors greater than this as it would result in a number bigger than long can handle. Could you confirm that for me.

Thanks.

I see, I think I may have missed some bits here sorry.

However, given that you iterate in reverse, starting at max values, that means as soon as you calculate a palindrome, you have the largest possible. So you can stop looping? Or have a missed the point again, and should just crawl into bed lol!


Edit: Maximum value of long is deffined by Long.MAX_VALUE == 2^63 -1

Chris