Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

# Thread: Efficiency problem

1. ## 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;

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;
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.  Reply With Quote

3. ## Re: Efficiency problem

Have you considered counting insteps of 11?

Chris  Reply With Quote

4. ## Re: Efficiency problem

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.  Reply With Quote

5. ## Re: Efficiency problem

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  Reply With Quote

6. ## Re: Efficiency problem Originally Posted by Freaky Chris 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

```
public long getLargestPalindrome1(){

for( long i = highValue; i > highValue/10 ; i = i - 1){

if(i  < factor2) return max;
//Here the method exits if i is smaller than the smallest factor of the current largest palindrome

for(long j = i ; j > highValue / 10; j = j - 1 ){

if(i % 11 == 0 || j % 11 == 0){

if(i*j < max) j = highValue/10;
//Here the j loop terminates if i*j is less than the current largest palindrome

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()```

I think I have addressed what you are talking about above. I am still trying to incorporate stepping down by 11 into the method so I'll post when get something.

Also the first palindrome I get is not necessarily the largest.

e.g. 2-digit factors, the answer is 9009 whose factors are 99 and 91
e.g. 3-digit factors, the answer is 906609 whose factors are 993 and 913.

I would of found a palindrome with i = 999 and j = some integer first but 993*913 was bigger than it.  Reply With Quote

7. ## Re: Efficiency problem

if you loop from highVal to highVal/10 for i and the same for j

you should always come across the largest possible palindrome first.

Chris  Reply With Quote

8. ## Re: Efficiency problem

If I do that for 3-digit factors, the first palindrome I find is

995*583 = 580085

which is smaller than 993*913 = 906609  Reply With Quote