# Calculate the largest palindromic number from the product of two 6-digit numbers (100000 to 999999)

Are there any efficient ways to solve this problem, for example using bitwise operator?

    public static boolean isPal(long num)
{
String numStr = Long.toString(num);
String rNumStr = "";

boolean result = false;

for (int i = numStr.length() - 1; i >= 0 ; --i)
rNumStr += numStr.charAt(i);

//System.out.println(numStr + "," + rNumStr);
try
{
if (Long.parseLong(numStr) == Long.parseLong(rNumStr))
result = true;
else
result = false;
}catch (NumberFormatException e) {
//System.err.println("Unable to format. " + e);
}
return result;

}

public static void calcPal(int rangeMin, int rangeMax)
{
long maxp = 0, maxq = 0, maxP = 0;
for (int p = rangeMax; p > rangeMin; p--)
for (int q = rangeMax; q > rangeMin; q--)
{
long P = p * q;
if (isPal(P))
if (P > maxP)
{
maxp = p; maxq = q; maxP = P;
}
}
System.out.println(maxp + "*" + maxq + "=" + maxP);
}

public static void main(String[] args)
{
calcPal(10, 99);
calcPal(100, 999);
calcPal(9000, 9999);
calcPal(10000, 99999);
calcPal(990000, 999999);
}


The largest palindrome which can be made from the product of two 2-digit (10 to 99) numbers is 9009 (91 × 99). Write a function to calculate the largest palindromic number from the product of two 6-digit numbers (100000 to 999999).

• it is my interview question – Selman Keskin Jul 5 '19 at 19:18

In an interview setting it is quite hard to come with an efficient solution (unless you happen to be very good in mental multiplication; however a $$\99 * 91\$$ example is a strong hint). The key to an efficient solution is an observation that

$$\999999 * 999001 = 999000000999\$$

is a quite large palindromic product. It means that you don't have to test the entire 6-digit ranges of multiplicands. It is enough to test multiplicands only in $$\[999001.. 999999]\$$ range. Just $$\10^6\$$ candidate pairs rather than $$\10^{12}\$$.

BTW, a similar identity holds for products of longer numbers as well.

Next, you may notice that there are just one thousand palindromic numbers larger than $$\999000000999\$$ (they are in form of 999abccba999), and to qualify as a solution is must have a 6-digit factor larger than $$\999001\$$. This implies the following algorithm (in pseudocode):

base = 999000000999
abc = 999
while abc >= 0
cba = reverse_digits(abc)
number = base + abc * 1000000 + cba * 1000
for factor in 999001 to sqrt(number)
if number % factor == 0:
return number
abc -= 1


The reverse_digits of a 3-digit number could be done extremely fast (a lookup table, for example). Still a $$\10^6\$$ or so rounds, but no expensive tests for palindromicity.

All that said, since the problem stems from Project Euler #4 it is possible that it admits a more elegant number-theoretical solution.

## Bug

    for (int p = rangeMax; p > rangeMin; p--)
for (int q = rangeMax; q > rangeMin; q--)


You are not including rangeMin in either of the loops, so you will never test products which involve the lower limit. You want >= in the loop condition:

    for (int p = rangeMax; p >= rangeMin; p--)
for (int q = rangeMax; q >= rangeMin; q--)


## Commutativity

Note that p * q == q * p, so you don't need to test all combinations in the range:

    for (int p = rangeMax; p > rangeMin; p--)
for (int q = rangeMax; q > rangeMin; q--)


Only the ones where either p >= q or q >= p, which will reduce your search space by close to 50%! For example, you could change the q range to start at the current p value and go down from there:

    for (int p = rangeMax; p >= rangeMin; p--)
for (int q = p; q >= rangeMin; q--)


## Test order: Fastest tests first!

isPal(P) is an involved function which will take a bit of time. In comparison, P > maxP is blazingly fast. So instead of:

            if (isPal(P))
if (P > maxP)
{
maxp = p; maxq = q; maxP = P;
}


            if (P > maxP)
if (isPal(P))
{
maxp = p; maxq = q; maxP = P;
}


## Early termination

If p*q is ever less than maxP, then multiplying p by any smaller value of q is a waste of time; you can break out of the inner loop, and try the next value of p.

If p*p is ever less than maxP, and the inner loop only multiplies p by q values which a not greater than p, then you can break out of the outer loop, too!

## String Manipulation

The following is inefficient, because temporary objects are being created and destroyed during each iteration.

    for (int i = numStr.length() - 1; i >= 0 ; --i)
rNumStr += numStr.charAt(i);


It is much better to use a StringBuilder to build up strings character by character, because the StringBuilder maintains a mutable buffer for the interm results.

Even better, it includes the .reverse() method, which does what you need in one function call.

StringBuilder sb = new StringBuilder(numStr);
String rNumStr = sb.reverse().toString();


## Unnecessary Operations

Why convert numStr to a number using Long.parseLong(numStr)? Isn't the result simply num, the value that was passed in to the function?

Why convert rNumStr to a number? If num is a palindrome, then aren't numStr and rNumStr equal?

public static boolean isPal(long num)
{
String numStr = Long.toString(num);
StringBuilder sb = new StringBuilder(numStr);
String rNumStr = sb.reverse().toString();

return numStr.equals(rNumStr);
}

• Very minor nitpick: "Fastest tests first" is a reasonable heuristic but even from a speed perspective is not the only axis worth considering. "Most selective test first" is also a reasonable heuristic, and the interplay between test speed and selectivity is intricate. I suspect without measurement that you're right in this case that the quicker test is a good filter, but perhaps it wants fleshing out why. – Josiah Jul 5 '19 at 22:53
• In this particular case, as mentioned "you could change the q range to start at the current p value and go down from there." You could do one better than that, and start q at maxP / p if larger. That could allow the P > maxP test to be removed altogether. – Josiah Jul 5 '19 at 23:00