Sorry if this is felt to be somewhat off-topic as my issue is the math and not the rust code. I'm working through some problems on leetcode. The largest palindrome product problem has me puzzled. The following code is successful and fast:
pub fn largest_palindrome(n: i32) -> i32 {
if n == 1 { return 9 }
let min_factor = (10_i32.pow(n as u32 - 1)) as i64;
let max = (10_i32.pow(n as u32)-1) as i64;
let max_factor = (max / 11) * 11;
for i in (min_factor..=max).rev() {
let palindrome = build_palindrome(i, n);
let lower = (palindrome as f64).sqrt().floor() as i64 - ( n as i64 * 121);
let limit = if lower <= 0 { 1 } else { lower };
for j in (limit..=max_factor).rev().step_by(11) {
if palindrome % j == 0 && (palindrome / j) / (max+1) == 0 {
return (palindrome % 1337) as i32
}
}
}
-1
}
fn build_palindrome(i: i64, n: i32) -> i64 {
let mut x = i * 10_i64.pow(n as u32);
let mut y = i;
let mut pal = 0;
while y > 0 {
pal = 10 * pal + y % 10;
y /= 10;
}
pal += x;
pal
}
I don't understand why a lower limit of the square root of the palindrome is not low enough to capture all the factors of n digit length. If you iterate from the maximum value to the square root, you cover all the possible factors b/c any factor less than the square root has the corresponding factor greater than the square root. Can someone explain the math for why that is not the case?
Follow up, I do not have a mathematical basis for my "fudge factor" of n * 121 other than a vague notion that it should be a multiple of 11 b/c palindrome. I found through trial and error a factor of 44 * (n - 2) also worked, but have no idea why. Any mathematical explanation for finding the true lower limit necessary to cover all factors of n digit length would be appreciated. Thanks.
Find the largest palindrome made from the product of two n-digit numbers.
Since the result could be very large, you should return the largest palindrome mod 1337.
So the algorithm is taking every n digit number in descending order and creating a palindrome of 2n digits by mirroring that number. Since the palindrome is always of even length digits, it must be divisible by 11. Thus one of the factors must be divisible by 11. If I check every possible factor of n digits, however, the algorithm takes much too long above n = 4 or 5, even if I only take factors that are divisible by 11. My assumption is that I should be able to limit the factors needing to be checked to only those >= the square root of the palindrome because any factor less than the square root would have a corresponding factor greater than the square root.
If the other factor is >= 10^n then it has too many digits and is rejected. Also the smallest factor j to be checked will always be n digits in length. Both factors must be n digits in length.
Let n = 2 and palindrome = 1001. Then you wont check 11 because it's less than sqrt(1001) ~= 31 and you wont check 91 because it's not a multiple of 11.
Yes but because we are looking for the greatest possible product, I assume that the palindrome is close to 10.pow(n). I'm checking all palindromes until I find one with two n length factors. I am hoping not to check all factors.
I'm sure something similar can happen with the larger palindromes too. If both factors must be of n digits, who says it has to be possible to move the 11 factor into the larger half of the product? Maybe the smaller half is less than the square root, even if the larger isn't.
Why are odd-length digit strings excluded from the space of potential products? Surely 14641 = 121^2 = 11^4, where n = 3, is a palindrome. 14641 is the product of two 3-digit numbers: 121 and 121.
Yes, but the problem is not to find any palindrome that is the product of n-digit numbers. It is specifically to find the largest product of n-digit numbers that is a palindrome. Since palindromes with k digits where k is even will always be larger than those where k is odd, I ignore the odd length palindromes. It might be possible that for very large values of n this is not a sound strategy but it turns out to be valid for 0 < n < 9.
In fact my assumption that the larger factor will be the one divisible by 11 for the larges palindrome is true for that range excepting n = 3 and n = 7. Extending the search only slightly below the square root finds the correct factors in those cases, yielding the fastest algorithm I can come up with for now. Without that lower limit the search takes far too long for n > 6.