## Friday, August 11, 2017

### LeetCode 477 - Largest Palindrome Product

https://leetcode.com/problems/largest-palindrome-product
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].

```输入范围n∈[1, 8]，除n = 1以外，其余n值最大回文数palindrome的位数均为偶数，可以拆分为half与reversed(half)左右两半

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
1. 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);
...
}
``````
2. 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.
}
``````
3. 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.
``````
4. 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];
}``````
https://discuss.leetcode.com/topic/74372/an-easy-9-line-java-solution
``````    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;
}``````