find max palindrome that is the product of two n-digit factors

n___ | factor range____ | palindrome range |
---|---|---|

2 | 10..99 | 100..9801 |

3 | 100..999 | 10000..998001 |

4 | 1000..9999 | 1000000..99980001 |

...

there are odd length palindromes e.g. 191 and even length palindromes e.g. 9779. In this problem both are possible, but the even are more likely because the largest is required and there are many even before the first odd comes.

Two ways to find palindromes that are products of n-digit integers:

- create all products with possible factors and check if the product is a palindrome. The problem is the order of the products which requires space and adds complexity. I didn't follow this further.
- create palindromes in decreasing order and check if it can be created by the multiplication of two factors with given range. There will be roughly 10^n such palindromes. Checking whether such a number is the product of two n-digit integers requires trying dividing that palindrome approx. its square root times. But there are limits on the numbers that heavily reduce work:
- avoid double checking e.g. 1
*9 = 9*1: iterate only from 1 to 9^(1/2) (square root of 9) - if e.g. the number can't be greater than 9, do not try 9*x < palindrome --> min-to-try = ceiling(palindrome / 9)

- avoid double checking e.g. 1

```
public int largestPalindrome(int n) {
if(n < 1 || n > 8) throw new IllegalArgumentException();
long factMin = (long)Math.pow(10, n - 1); // e.g. 10^(3-1) = 100
long factMax = factMin * 10 - 1; // e.g. 100*10 - 1 = 999
for(long left = factMax * factMax / (factMin * 10); left >= factMin; left--) {
long palindrome = createEvenPalindrome(left);
if(findProduct(palindrome, factMin, factMax) != 0)
return (int)(palindrome%1337L);
}
for(long left = factMin * 10 - 1; left >= factMin; left--) {
long palindrome = createOddPalindrome(left);
if(findProduct(palindrome, factMin, factMax) != 0)
return (int)(palindrome%1337L);
}
return 0;
}
// returns x so that product % x == 0 or 0 if no x exists.
// x must be in the inclusive range [factMin, factMax]
static private long findProduct(long product, long factMin, long factMax) {
factMin = Math.max((product + factMax - 1) / factMax, factMin); // max(ceiling(product / factMax), factMax)
factMax = Math.min((long)Math.sqrt((double)product), factMax);
for(long mul = factMin; mul <= factMax; mul++) {
if(product % mul == 0) return mul;
}
return 0;
}
// creates an even palindrome by mirroring the given part on the right.
// e.g. left = 123 --> return 123321
static private long createEvenPalindrome(long left) {
long palindrome = left;
for(; left > 0; left /= 10)
palindrome = palindrome * 10L + (left % 10);
return palindrome;
}
// creates an odd palindrome e.g. 123 --> 12321
static private long createOddPalindrome(long left) {
long palindrome = left;
for(left /= 10; left > 0; left /= 10)
palindrome = palindrome * 10L + (left % 10);
return palindrome;
}
```