fourteen 、 Maximum palindrome product

14.1、 Question design requirements

Given an integer n , return Can be expressed as two n Of the product of bit integers Maximum palindrome integer . Because the answer can be very big , So return it to 1337 Remainder .

 Example  1:
 Input ：n = 2
 Output ：987
 explain ：99 x 91 = 9009, 9009 % 1337 = 987

 Example  2:
 Input ： n = 1
 Output ： 9

 Tips :
1 <= n <= 8

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/largest-palindrome-product

14.2、 Their thinking

The first solution ：

First calculate the maximum product , Then take out the first half of the maximum product and use the generation function to generate the corresponding palindrome number , Then compare the generated palindromes , If not found, subtract the first half of the number and regenerate a new palindrome number for comparison , Go on in turn ; If it is found, output it .

The second solution ：

Because the scope of this question is fixed and relatively small , Just type the meter directly .

14.3、 Algorithm

The first algorithm ：

class Solution {
    
    public int largestPalindrome(int n) {
    
        // If n by 1, only 9 Maximum 
        if (n == 1) {
    
            return 9;
        }
        // Definite boundary 
        long upper = (long) Math.pow(10,n) - 1;
        long lower = upper/10 + 1;
        // The maximum product in the range 
        long maxNumber = upper * upper;
        // Calculate the first half of the maximum number 
        long half = (long) (maxNumber/Math.pow(10,n));
        // Whether to find 
        boolean found = false;
        // Return value 
        long result = 0;
        // Loop to find the corresponding number of palindromes 
        while (!found){
    
            // Call build function 
            result = create(half);
            // Search from high to low 
            for (long i = upper; i >= lower; i--) {
    
                //i*i The value is less than result Value 
                if (i * i < result){
    
                    break;
                }
                //result Yes i Take remainder as 0
                if (result % i == 0){
    
                    found = true;
                    break;
                }
            }
            // Did not find , Then look for the next digit in the first half 
            half--;
        }
        // Returns the number of palindromes and returns to 1337 Remainder 
        return (int) (result % 1337);
    }

    // Generating function 
    public long create(long number){
    
        // Splice the first half of the transmitted number with the first half of the number generated by flipping to generate a new palindrome number 
        String str = number + new StringBuilder().append(number).reverse().toString();
        return Long.parseLong(str);
    }
}

Reference video ： Power button up Lord Guo

The second algorithm ：

class Solution {
    
    public int largestPalindrome(int n) {
    
        int[] palindromes = {
    9,987,123,597,677,1218,877,475};
        return palindromes[n - 1];
    }
}