https://leetcode.com/problems/largest-palindrome-product
https://leetcode.com/problems/largest-palindrome-product/discuss/96306/Java-solutions-with-two-different-approaches
http://blog.csdn.net/sheldon0227/article/details/64922216
http://www.tonyliu.info/2017/03/16/Algorithms-479
X. https://blog.csdn.net/magicbean2/article/details/78683871
long long ret[8] = {9, 9009, 906609, 99000099, 9966006699, 999000000999, 99956644665999, 9999000000009999};
return ret[n - 1] % 1337;
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.
Example:
Input: 2
Output: 987
Explanation: 99 x 91 = 9009, 9009 % 1337 = 987
Note:
The range of n is [1,8].
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:
- How to construct the palindromes and arrange them in descending order (note we are interested in the maximum palindrome).
- How to test if a given palindrome can be written as the product of two
n-digitnumbers.
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, further check if 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) break; // terminate if the other number is greater than current 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
http://bookshadow.com/weblog/2017/01/05/leetcode-largest-palindrome-product/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.
解法I 构造回文+校验除数
public int largestPalindrome(int n) {
if (n == 1) {
return 9;
}
int high = (int) Math.pow(10, n) - 1, low = high / 10;
for (int i = high; i > low; i--) {
long palindrome = createPalindrome(i);
for (long j = high; j > low; j--) {
if (palindrome / j > high) {
break;
}
if (palindrome % j == 0) {
return (int) (palindrome % 1337);
}
}
}
return -1;
}
private long createPalindrome(long num) {
String str = num + new StringBuilder(Long.toString(num)).reverse().toString();
return Long.parseLong(str);
}http://blog.csdn.net/sheldon0227/article/details/64922216
http://www.tonyliu.info/2017/03/16/Algorithms-479
- Search all the palindrome in [10^(2n - 1), 10^(2n)]. (from big to small)
e.g.for (int i = 10 ^ n - 1; i >= 10 ^ (n - 1); i--) { pal = i append inverse(i); ... } - Check if the number is a product of two n-digit number. e.g.
// Givn i, check if i is a product of two n-digit number: for (int j = 10 ^ (n - 1); j <= sqrt(i); j++) { if (pal % j == 0 && len(pal/j) == n) // then i is the answer. } - Build a palindrome from a number:
// convert num to string. // invert the string using reverse(). // append the new string to the old string. // convert string to num. // return num. - Complexity: O(10^n) * O(10^(n/2) = O(10^((3/2)n))
So when n == 8, we have 10^12 times of check, which is large, but fortunately the answer is near to the upper bound so in practice it’s very fast.
int largestPalindrome(int n) {
if (1 == n) return 9; // Since there is only 1 digit in the palindrome, we can't generate it using below method.
// Search from max possible value of num1 to the min possible value of num1.
int upper = pow(10, n) - 1, lower = pow(10, n - 1);
for (int i = upper; i >= lower; i--) {
long cand = buildPalindrome(i);
for (int j = upper; j >= cand / j; j--) {
if (0 == cand % j && to_string(cand / j).size() == n) {
return cand % 1337;
}
}
}
return -1;
}
// turn "abc" to "cba"
long buildPalindrome(int n) {
string str = to_string(n);
reverse(str.begin(), str.end());
return stol(to_string(n) + str);
}
// Run all the possible input and record them. O(1)
int answer(int n) {
int ans[10] = {0, 9, 987, 123, 597, 677, 1218, 877, 475};
return ans[n];
} public int largestPalindrome(int n) {
if (n==1) return 9;
int max=(int)Math.pow(10, n)-1;
for (int v=max-1;v>max/10;v--) {
long u=Long.valueOf(v+new StringBuilder().append(v).reverse().toString());
for (long x=max;x*x>=u;x--)
if (u%x==0)
return (int)(u%1337);
}
return 0;
}Part III -- From product to palindrome
Similar to the first approach, we need to consider the following two problems:
- How to construct the products and arrange them in descending order.
- 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 orderX. https://blog.csdn.net/magicbean2/article/details/78683871
１、查表法：既然题目中说了ｎ的范围是[1, 8]，那么我们提前计算出8个结果存放在表中，在函数中直接返回即可。还有谁比我更流氓？
int largestPalindrome(int n) {long long ret[8] = {9, 9009, 906609, 99000099, 9966006699, 999000000999, 99956644665999, 9999000000009999};
return ret[n - 1] % 1337;
