Largest Palindrome Product

This page explains Java solution to problem Largest Palindrome Product using Math algorithm.

Problem Statement

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.

Input: 2
Output: 987
Explanation: 99 x 91 = 9009, 9009 % 1337 = 987

Solution

package com.vc.hard;

class LargestPalindromeProduct {
    public int largestPalindrome(int n) {
        int hi = (int) Math.pow(10, n) - 1;
        int lo = hi / 10;
        for(int left = hi; left > lo; left--) {
            StringBuilder sb = new StringBuilder(Integer.toString(left));
            long palindrome = Long.parseLong(sb.toString() + sb.reverse().toString());

            for(long cand1 = hi; cand1 > lo; cand1--) {
                long cand2 = palindrome / cand1;
                if(cand2 > cand1) break;
                if(palindrome % cand1 == 0) return (int)(palindrome % 1337L);
            }
        }
        return 9;
    }
}

Time Complexity

O(9 * 10^{2n - 2})

Space Complexity

O(1)