479. Maximum palindromic number product: Enumeration application

Make writing a habit together! This is the 16th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

Topic describes

This is LeetCode on the 479. Maximum palindrome number product, difficulty is difficult.

Tag: “enumeration”, “math”

Given an integer NNN, returns the largest palindrome integer that can be represented as the product of two NNN bit integers.

Because the answer could be very large, return it mod 133713371337.

Example 1:

Input: N = 2 Output: 987 Description: 99 x 91 = 9009, 9009%1337 = 987Copy the code

Example 2:

Input: n = 1 Output: 9Copy the code

Tip:

• 
  $1 <= n <= 8$

Enumeration + Math

For two numbers with digit number NNN, the number of bits in their product is either 2∗n2 * n2∗n, or 2∗n−12 * n-12 ∗n−1.

When the digit n>1n >1n >1, we can always find the answer at the digit 2∗n2 * n2∗n.

Taking advantage of the property of palindromes, we only need to enumerate the first half of the palindromes (the second half is uniquely determined). We only need to proceed “from largest to smallest” in the first half of the enumeration to ensure that the first legal value found is the largest number, which is 10n−110^ n-110n −1 for an NNN digit.

Specifically, when enumerating to the first half of the palindrome string III, we use the palindrome string characteristics to construct and issue the actual palindrome value numsnumsnums, and then check whether numsnumsnums can be decomposed into number pairs (a,b)(a, B)(a, B) with digit number NNN, using multiplication with the commutative law, We only need the larger number in the enumerator pair.

Code:

class Solution {
    public int largestPalindrome(int n) {
        if (n == 1) return 9;
        int max = (int) Math.pow(10, n) - 1;
        for (int i = max; i >= 0; i--) {
            long num = i, t = i;
            while(t ! =0) {
                num = num * 10 + (t % 10);
                t /= 10;
            }
            for (long j = max; j * j >= num; j--) {
                if (num % j == 0) return (int)(num % 1337); }}return -1; }}Copy the code

• Time complexity: the complexity of the first half of the enumeration palindrome string is O(10n)O(10^n)O(10n); Check whether the palindrome string can be decomposed to O(10n)O(10^n)O(10n). The overall complexity is O(102n)O(10^{2n})O(102n)
• Space complexity: O(1)O(1)O(1)

The last

This is the No.479 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode as of the start date, some of which have locks, we will first finish all the topics without locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.