Java solutions with two different approaches


  • 8
    F

    There are two directions for approaching the problem: one is to first construct the palindrome and then test whether it can be written as the product of two n-digit numbers; the other is to first obtain the product of the two n-digit number and then test whether the product is a palindrome.


    Part I -- From palindrome to product

    It looks like most of the posts here took the first approach, so I will start from the first one also. For this approach, we need to consider the following two problems:

    1. How to construct the palindromes and arrange them in descending order (note we are interested in the maximum palindrome).
    2. How to test if a given palindrome can be written as the product of two n-digit numbers.

    For the first problem, we need to know how many digits in each of the palindrome. Since the palindrome is meant to be the product of two n-digit numbers, it can have either 2n or 2n - 1 digits. And since we are interested in maximum palindrome, those with 2n digits will be considered first. These palindromes can be divided into two parts with equal number of digits (n for each part): left and right. And left will be a mirror image of right, and vice versa. Therefore each palindrome will be fully determined by either its left or right part.

    Note the left part is an n-digit number and if we arrange it in descending order, the resulted palindrome will also be in descending order. Therefore we may start from the maximum n-digit number and go towards the minimum n-digit number. For each number, we can construct the palindrome by concatenating the number with its mirror image.

    Now we come to the second problem, i.e., how to check if the constructed palindrome can be written as the product of two n-digit numbers. This is essentially the "integer factorization" problem. One straightforward way would be the "trial division" algorithm, i.e., test each of the n-digit number to see if it is a factor of the palindrome and if so, the other factor is also an n-digit number.

    Here is the java problem for this approach. Note we only considered palindromes with 2n digits. Fortunately for each case (n = 1 to 8), we are able to find at least one palindrome that can be decomposed into two n-digit numbers, therefore there is no need to check those with 2n - 1 digits (However if you are still concerned, refer to this post).

    public int largestPalindrome(int n) {
        long max = (long)Math.pow(10, n) - 1;
        long min = max / 10;
            
        for (long h = max; h > min; h--) {
            long left = h, right = 0;
            for (long i = h; i != 0; right = right * 10 + i % 10, i /= 10, left *= 10);
            long palindrom = left + right;      // construct the palindrome
                
            for (long i = max; i > min; i--) {
                long j = palindrom / i;
                if (j > i || j <= min) break;     // terminate if the other number is greater than current number or is not an n-digit number
                if (palindrom % i == 0) return (int)(palindrom % 1337); // found if current number is a factor
            }
        }
    
        return 9;    // account for case n = 1
    }
    

    Apparently the algorithm goes exponentially: O(10^n)


    Part II -- Observations and optimizations

    Before I continue to the other approach, I'd like to point out some observations and the corresponding optimizations.

    As I mentioned, we are interested in the maximum palindrome, thus it's reasonable to first check palindromes starting with digit 9. If not found, then those starting with digit 8, 7, 6,.... If the palindrome is starting with digit 9, it must also be ending with digit 9. Now if the palindrome is the product of the two n-digit numbers, the two numbers must be ending with digits 1, 3, 7, or 9. Similarly for other cases.

    It looks like for each n, there exists at least one palindrome with 2n digits and starting with digit 9 that can be written as the product of two n-digit numbers. I was able to prove for the case when n is even, but failed for the case when n is odd.

    If n is even, let n = 2k. The two n-digit numbers can be num1 = 10^n - 1 and num2 = 10^n - 10^k + 1. Their product will be p = num1 * num2 = 10^(3k) * (10^k - 1) + (10^k - 1) = 9..0..9, where p will have k leading and trailing digit of 9 and 2k digit 0 in the middle. For n <= 8, this is also the maximum palindrome that is found (not sure if it holds true for higher n, but most likely it will do).

    If n is odd, the above trick does not work (p will have unbalanced 9's). For this case, however, I would like to propose the following statement: let n = 2k + 1, there exists at least two n-digit numbers num1 and num2, 10^n - 10^(k+1) <= num1, num2 <= 10^n - 1, whose product will be a palindrome (verified for n <= 8).

    In summary, we have the following conclusion: for each n, there exists at least two n-digit numbers num1 and num2, 10^n - 10^m <= num1, num2 <= 10^n - 1 and m = [(n+1)/2], whose product will be a palindrome.


    Part III -- From product to palindrome

    Similar to the first approach, we need to consider the following two problems:

    1. How to construct the products and arrange them in descending order.
    2. How to test if a given product is a palindrome.

    The second problem is easy, simply reverse the product and check if it is the same as the original product. The first problem, however, is a little tricky. Obtaining the product is a no-brainer. The hard part is how to arrange them in descending order.

    First we need to determine the candidate products. From part II, we will only consider products obtained with the two n-digit numbers in the range [10^n - 10^m, 10^n - 1]. Second we will use a PriorityQueue to extract these candidate products in descending order.

    However, the total number of candidates above still blows up the memory when n = 8. So we need further pruning. First again since the product ends with digit 9, the two numbers must be ending with digits 1, 3, 7, or 9. Second, to avoid repetition, the first number will be no less than the second. Third, for all products obtained with the first number fixed, there is no need to include them all at once but instead we can consider them once at a time with the second number going in decreasing order. So eventually we end up storing the two numbers in the PriorityQueue while extracting them according to their product.

    With these optimizations, here is the java program for this approach:

    public int largestPalindrome(int n) {
        int max = (int)Math.pow(10, n) - 1;
        int min = max - (int)Math.pow(10, (n + 1) >> 1);
        	
        Comparator<int[]> cmp = new Comparator<int[]>() {
        	@Override
    	public int compare(int[] a, int[] b) {
        	    return Long.compare((long)b[0] * b[1], (long)a[0] * a[1]);
        	}
        };
        	
        PriorityQueue<int[]> pq = new PriorityQueue<>(max - min, cmp);
        	
        for (int i = max; i > min; i--) {
        	int r = i % 10;
        		
        	if (r == 3 || r == 7) {
        	    pq.offer(new int[] {i, i});
        	} else if (r == 1) {
        	    pq.offer(new int[] {i, i - 2});
        	} else if (r == 9) {
        	    pq.offer(new int[] {i, i - 8});
        	}
        }
        	
        while (!pq.isEmpty()) {
        	int[] a = pq.poll();
        	long p = (long)a[0] * a[1];
        		
        	if (isPalindrome(p)) return (int)(p % 1337);
        		
        	if (a[1] > min) {
        	    a[1] -= 10;
        	    pq.offer(a);
        	}
        }
        
        return 0;
    }
        
    private boolean isPalindrome(long z) {
        long r = 0;
        for (long x = z; x != 0; r = r * 10 + x % 10, x /= 10);
        return r == z;
    }
    

    This algorithm still goes exponentially with n while also requires extra space of the same order.


  • 0

    I urge everybody to read this article. It is a little long but I am grateful that I did not skip it. It is not the panacea for this problem, but it does teach me a lot. Thanks for sharing.


  • 0
    V

    @vegito2002 very true.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.