Largest palindrome made from the product of two 3-digit numbers

Question

I am working on an interview question in which I need to find the largest palindrome made from the product of two 3-digit numbers. Here is the question.

public class PalindromeThreeDigits {

    public static void main(String[] args) {
        int value = 0;
        for(int i = 100;i <=999;i++) {
            for(int j = i;j <=999;j++) {
                int value1 = i * j;
                StringBuilder sb1 = new StringBuilder(""+value1);
                String sb2 = ""+value1;
                sb1.reverse();
                if(sb2.equals(sb1.toString()) && value<value1) {
                    value = value1;
                }                    
            }
        }

        System.out.println(value);
    }
}

Are there any optimizations/simplifications that we can do in this program?

Answer 1

When checking to see if a number is a palindrome, you effectively do:

StringBuilder sb1 = new StringBuilder(""+value1);
String sb2 = ""+value1;
sb1.reverse();
if(sb2.equals(sb1.toString()) && ....) {

That should be extracted to a function:

private static boolean isPalindromeSB(final int value1) {
    StringBuilder sb1 = new StringBuilder(""+value1);
    String sb2 = ""+value1;
    sb1.reverse();
    return sb1.equals(sb2);
}

so that you can use it as follows:

if (isPalindromeSB(value1) && ....) {

That neatens up your code, and does what is called "Functional Extraction".

Additionally, if you look at that function it does a lot of work... it does 2 string concatenations, creating three Strings, a StringBuilder, and a bunch more.

It would be more efficient to keep everything as numbers, and have a function like:

private static boolean isPalindrome(final int product) {
    int p = product;
    int reverse = 0;
    while (p != 0) {
        reverse *= 10;
        reverse += p % 10;
        p /= 10;
    }
    return reverse == product;
}

Note that this creates only two int values.... and it loops once per digit.

I tested it, and it is about 4 times faster than the String version.

Answer 2

String abuse is one of my pet peeves. So, I'm going to focus on that.

The block of code:

StringBuilder sb1 = new StringBuilder(""+value1);
String sb2 = ""+value1;
sb1.reverse();
if(sb2.equals(sb1.toString()) && value < value1) {
    value = value1;
}

The bit of code ""+value1 will:

• Create a String Builder
• Append the empty string to it.
• Append the value1 cast as a String to it.
• Convert the implied StringBuilder to a String

... which then is used as an argument to a StringBuilder. Which you incidently then do again to assign to the string sb2 on the next line. All of this to get the reverse() method from the StringBuilder.

This creates lots of unnecessary objects. Others address the better palindrome detection code - which is better than the use of the String and StringBuilder to do it.

If one was to continue on the path of using Strings and StringBuilders here, lets instead look at other options for the StringBuilder construction and ""+value1 on the next line.

You know that the size for value1 is no more than 6 characters long (log₁₀(999 * 999) = 5.99913097645). So, instead initialize the StringBuilder with the known size.

StringBuilder sb1 = new StringBuilder(6);

Next, the ""+value1 can be done without the implied StringBuilder using Integer.toString(int i) method (javadoc).

String sb2 = Integer.toString(value1);

And then, you can either approach this as an append to the StringBuilder, or forget that entire bit about the log₁₀ and use it as the constructor instead.

This would give you:

String sb2 = Integer.toString(value1);
StringBuilder sb1 = new StringBuilder(sb2);

or

StringBuilder sb1 = new StringBuilder(6);
String sb2 = Integer.toString(value1);
sb1.append(sb2);

I should point out that neither of these are optimal (they are far from it). Rather, they are demonstrating ways to be less abusive of String and StringBuilder creation and should get one thinking about where Strings and StringBuilders are implicitly created and ways to avoid it. For this particular case, there are even simpler approaches such as using the .append(int) method which does the conversion for you.

StringBuilder sb1 = new StringBuilder(6);
sb1.append(value1);
String sb2 = sb1.toString();
String sb3 = sb1.reverse().toString();
if(sb2.equals(sb3) && value < value1) {
    value = value1;
}

Note again that this is generally inferior to approaching this with the integer solutions described in other answers. I'm just trying to point out the "this is creating lots of excess objects and you should think about what you are actually doing when you use the ""+... construct with a String (or even worse, the += for a String) and the hidden costs that implies. Its not a big problem here, but I've dealt with such coding styles that were creating and throwing away hundreds of kilobytes of Strings thousands of times in a loop (and let me tell you, gc was not a happy place on that machine).

Answer 3

Two types of improvements can be made:

• Prune the search space
• optimize the checking step for each item in the search space

First type is a first order improvement that can lead to exponential improvement in the runtime and any reduction of this step will also remove the need to do the checking step. Second type is a second order improvement which at most will lead to a linear improvement in the runtime.

For first type improvement, I'd do the following which makes sure I only loop through numbers which are larger than the palindrome I've already found (therefore no checking is needed to see if new palindrome is larger.. note that if you have this check, by the time you get to it, you have already lost the exponential speedup potential of pruning the search space and this check only provides at most a linear speedup.. the below approach actually prunes the search space):

find_largest_pali():
   largest_pali = 0;
   for x from 999 downto 100:
     for y from 999 downto max(x, largest_pali/x):
       largest_pali = return_larger_pali(x*y, largest_pali);

I am not going to focus on any number theoretic improvements (like knowing certain palindromes or what palindromes factor into) since this is a programming assignment not a math problem.

Now for the second order type improvement: Arithmetic operations are much much much faster than any string manipulation. So stick to math operations (divide, mod, compare, e tc.)

A small helper function to extract a digit:

digit(number, position)
   return (number/position) mod 10;

Now the palindrome checking function: note that compare is abandoned if any digit fails the checking. With the string approach, yo u need to make full string translatioons and reversing to decide if a palindrome is found)

return_larger_pali(candidate_pali, prev_pali)
  if (candidate_pali between 10000 and 99999)
     if( digit(candidate_pali,  1) != digit(candidate_pali, 10000)) return prev_pali;
     if( digit(candidate_pali, 10) != digit(candidate_pali, 1000 )) return prev_pali;
     // no need to check digit in position 100
  else
  if (candidate_pali between 100000 and 999999)
     if( digit(candidate_pali,   1) != digit(candidate_pali, 100000)) return prev_pali;
     if( digit(candidate_pali,  10) != digit(candidate_pali, 10000 )) return prev_pali;
     if( digit(candidate_pali, 100) != digit(candidate_pali, 1000  )) return prev_pali;
  end if
  return candidate_pali

Another approach which will probably be more suitable for larger range of numbers is to precompute the digit-reverse (e,g, digit-reverse of 123 is 321) for numbers less than 1000 and use a lookup method to check if the upper half digits of a number is equal to the digit-reverse of its lower half (hence a palindrome). This approach uses arrays and memory ops whose overhead may waste any gains made by the lookup method so some benchmarking is needed before one can decide between the two approaches.

Here's an outline for a function using a lookup table:

digit(number, position)
   return (number/position) mod 10;

find_largest_pali_using_lookup():
   // prcompute digit-reverse
   lookup_arr = array[1000];
   for i from 999 downto 0
      lookup_arr[i] = 100*digit(i,1)+10*digit(i,10)+digit(i,100);

   largest_pali = 0;
   for x from 999 downto 100:
     for y from 999 downto max(x, largest_pali/x):
       largest_pali = return_larger_pali_using_lookup(x*y, largest_pali, &lookup_arr);


return_larger_pali_using_lookup(candidate_pali, prev_pali, lookup_arr)
  if (candidate_pali between 10000 and 99999)
     if( (candidate_pali/100) != lookup_arr[candidate_pali mod 1000] ) return prev_pali;
  else
  if (candidate_pali between 100000 and 999999)
     if( (candidate_pali/1000) != lookup_arr[candidate_pali mod 1000] ) return prev_pali;
  end if
  return candidate_pali;

Notes for above outline:

• I am passing a pointer to the array to the check function (passing arrays around is very expensive)
• For the case where candidate_pali is less than 100000 above, I am comparing digits 0 through 2 against digits 2 through 4 (e.g., for 12345 I am comparing 123 to digit reverse of 345). This trick allows me to use the same lookup table for all cases. let me know if the trick is not obvious.

Note that I have used a verbose approach in above outline to make my intention clear. You could compress the programming and rewrite it in the following more compact form once the intention is understood:

return_larger_pali_using_lookup(cand, prev_pali, lookup_arr)
  return
     ( (cand/((cand<100000)?100:1000) = lookup_arr[cand mod 1000])? cand : prev_pali);

And ultimately if you really want to do everything in one function:

find_largest_pali_using_lookup():
   //init
   lookup_arr = array[1000];
   largest_pali = 0;
   // prcompute digit-reverse
   for i from 999 downto 0
      lookup_arr[i] = (100*(i mod 10))+(10*((i/10) mod 10))+(i/100);
   // find
   for x from 999 downto 100:
     for xy from 999*x downto max(x*x,largest_pali) decrement by x:
       if( ((xy)/(((xy)<100000)?100:1000) = lookup_arr[(xy) mod 1000]))
          largest_pali = xy;

Answer 4

I suggest you start from the top, rather than from the bottom. Like that, you can cross off more numbers faster. Because if you hit a number at the 500000 range, you know that 500000 divided by 999 is 500, and there's no more reason to check any number below 500.

Save for altering the algorithm like that, I'd move the check of value < value1 earlier. If the value is lower, don't bother checking if it's a palindrome.

Answer 5

1. Making the string
   • Use sb2=String.valueOf(value1); -- it emits the same bytecode but is more readable.
2. Reversing the string
   • Use sb2 as the argument to the StringBuilder constructor. sb1 = new StringBuilder(sb2); although the compiler probably does this anyway.
3. Use math
   • Loop over how many digits the palindrome might have. For your first case, only consider pairs of numbers that multiply to 100000 or greater. If you ever find a product that's less than 100000, don't bother decrementing any more.

Answer 6

How about a more efficient search strategy?

for x from 999 to 121:  // 121*121 is palindrome, don't go lower that that
  for y from 999 to x:  // only search upper triangle of this matrix
    z=x*y
    if z > maxPalindromeNumSoFar:  
      // only check palindrome-ism if z is bigger
      check z for palindrome-ism and replace if bigger

And add a bit of domain knowledge. 444,444 = 481*924, so further constrain the search range:

for x from 999 to 481:
  for y from 999 to max(x, 444444/x):

There's also a bit of number theory about palindromic numbers have factors of 11 or 101, not sure how best to integrate that info...