How can I optimise my awful code for finding the highest palindrome of a 3 digit number?

Question

This is what I have written so far. It compiles, and, as far as I can tell, it should 'work' - if you were to give your computer an infinite amount of time to compute the answer !

I was just wondering if anyone would please be able to give me a way to optimise this so that my program will tell me the highest palindromic number (the same both forwards and backwards eg, 91 * 99 = 9009;) formed by multiplying any two three-digit numbers.

 public class HighestPalindrome {
     public static void main(String[] args) {
    int number=0;
    int answer=0;

    search:
    for(int LoopOfFirstNumber=999;LoopOfFirstNumber<=100;LoopOfFirstNumber -= 3){
      for(int LoopOfSecondNumber=LoopOfFirstNumber;LoopOfSecondNumber<=100;LoopOfSecondNumber-=3)
      {
        number = LoopOfFirstNumber * LoopOfSecondNumber;
        if (number == reverse(number))
         {
          answer=number;
          System.out.println(answer);
          break search;
         }
      }
    }
  }

     //The code after this works fine, I believe. It will reverse any number given very quickly, I think the problem
     //is above....with the two for loops!

    private static int reverse(int n, int r) {
      if (n == 0) return r;
      System.out.println("This iteration returns " + n/10 + " and  " + 10*r+n%10);
      return reverse(n/10, 10*r+n%10);
    }

    public static int reverse(int n) {
     return reverse(n, 0);
    }

Answer 1

As you already guessed, the problem is in the nested loop. Try to figure out a few property of the numbers. Multiplication of two three digits number will always give a number having five or six digits. Since you are looking for the highest number, then it's expected to be six digit number starting with number 9 and since it's palindromic, it probably ends with number 9 as well. In short, you're expecting numbers in the form 9xyyx9.

Next, not all pairs of numbers can be multiplied and end with number 9. xx3 and xx3 will give xxxxx9, so does xx1 and xx9; but xx1 and xx8 will never multiply to xxxxx9.

Find properties like these, and try to filter which ones likely can be implemented easily into your search.

Answer 2

Your for loop conditions is wrong:

LoopOfFirstNumber<=0

it should be:

LoopOfFirstNumber>=100

You should continue to loop till your loop counters are >= 100 which is the smallest 3 digit number.

Also once you find a palindrome, you need to break both the loops. Currently you are breaking only the inner loop. To fix this you need to use labeled break.

Answer 3

The inner for loop doesn't need to start with 999, it can start with LoopOfSecondNumber = LoopOfFirstNumber:

Let's assume that there is a solution for which LoopOfSecondNumber = x > LoopOfFirstNumber = y. Then there would be a solution where the two numbers are switched: LoopOfFirstNumber = x, LoopOfSecondNumber = y => This solution would thus have been found earlier in the outer loop already.

This doesn't bring you much optimization though, in best case it takes you half of the time the original code took.

Answer 4

Why don't you tackle it from the other side?

Create a set of all the palindrome numbers starting from 1000000 (1000*1000) and working down, should be fairly easy.

And then factorise them - though I guess you're going to need an algorithm for this :-(