LargestPalindromeProductOPT [source code]
public class LargestPalindromeProductOPT {
static
/******************************************************************************/
public class Solution {
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);
}
}
/******************************************************************************/
public static void main(String[] args) {
LargestPalindromeProductOPT.Solution tester = new LargestPalindromeProductOPT.Solution();
int[] inputs = {
2, 987,
1, 9,
3, 123,
};
for (int i = 0; i < inputs.length / 2; i++) {
int n = inputs[2 * i];
int expected = inputs[1 + 2 * i];
System.out.println(Printer.seperator());
int output = tester.largestPalindrome(n);
System.out.println(Printer.wrapColor(n + "", "magenta") + " -> " + output + Printer.wrapColor(", expected: " + expected, (expected == output ? "green" : "red")));
}
}
}
这个是在一个中国人的博客上看到的一个解, 这个是完全没有hardcode的;
但是这个算法其实好像也是有问题的, 这个后面再说.
这种穷搜问题, 尤其是数学上的这种generate&test的问题, 其实也碰到过几次了, 为了提高搜索效率, 很多时候需要思考的一个问题就是, 我们最终搜索的应该是什么值. 比如之前一个sum of two squares的题目, 那个题目当时我一开始认为应该搜索平方值, 但是这个方法最后的速度很慢; 正确的做法应该是搜索平方根, 因为在这个问题里面, valid的平方根的percentage要远高于valid的平方值的percentage;
这个题目也是类似的. 其实我当时是想到这个问题的; 通过举例子, 我发现, 比如n等于8的时候, 最终的这个回文只可能是16(2 n)位或者15(2 n - 1)位. 当时我有想过, 或许搜索回文值会快一些? 但是当时对于回文值的value ordering and value domain没有任何的想法, 感觉就是一个permutation的穷搜, 未必会快很多;
但是他这个算法最后体现了, 还是搜回文快一些; 注意这个东西其实在425上课的时候有稍微讲过一点, 就是generate and test, 或者backtracking问题的时候, 我们的variable ordering的问题; 当然不完全一样, 因为那里的不同的variable之间是几乎没有直接的关联的, 而我们这里, 比如回文值, product, 和n位数自己之间是有直接的关联和对应的;
即便如此, 那里当时给出的一个重要结论就是, most constrained first, 这个按照老师当时的定义, 就是valid的存活率最小的就是most constrained? 好像这个概念的描述上面有点不对应;
反正类似这种的搜索问题, 如果比如有平方根和平方值这样的两种的对应, 肯定是搜索平方根, 因为平方根所可取的domain要比平方值小很多;
但是这个问题的算法其实也是不完美的, 比如这里他做出来的回文, 默认认为max回文肯定是偶数位的(比如16 for n = 8), 这个原作者在底下说了, 其实并没有办法给出严格的数学证明, 就是通过穷举(就8个答案)验证的; //但是实际上, 在代码上你也可以把两种情况都搜索了, 我感觉. 只不过因为是找最大值, 所以先搜的肯定是2n位的, 所以就算你形式上写了搜2n-1位回文的算法, 最后也是不会被execute的;
另外他这里构造回文的算法本身还是指的借鉴的. 我当时担心是一个permutation的问题, 所以不知道怎么搜, 不过看他这里的做法, 实际上就是一个数值increment的问题; 反正你真正碰到这种permutation搜索的问题的时候, 你也只能往这种类似0..n的搜索上面靠, 因为这个是简单循环唯一能解决的搜索问题;
注意他这里搜索回文值(product)而不是n位数(operand of multiplication)还有一个好处, 就是直接第一个碰到的就可以确定是max; 我自己的用搜索n位数的时候也是从上往下搜, 但是实际上第一个碰到的并不一定是最大的, 这个也不知道是什么原因;
discussion的最优解也是用这个方法做得;
这个是下面多这个问题给出的一个caveat:
For n from 2 to 9, the largest palindromes are 2n digits. However, with the same algorithm, when n is 10 the palindrome returned is 18 digits, but it's possible that there is one larger palindrome which is with 19 digits.
For n from 2 to 8 as noted by the question, the algorithm is safe.
n = 2
palindrom is: 9009
number returned: 987
n = 3
palindrom is: 906609
number returned: 123
n = 4
palindrom is: 99000099
number returned: 597
n = 5
palindrom is: 9966006699
number returned: 677
n = 6
palindrom is: 999000000999
number returned: 1218
n = 7
palindrom is: 99956644665999
number returned: 877
n = 8
palindrom is: 9999000000009999
number returned: 475
n = 9
palindrom is: 999900665566009999
number returned: 1226
n = 10
palindrom is: 461168600006861164
number returned: 670
所以说这个问题其实是高度局限性的, 就是玩弄人的感觉, 难怪downvote是到目前见过的最多的(125/133);
还有一些其他的搜索算法, 不过核心思路都是回文product从大到小的搜索; 变化主要体现在怎么验证每一个回文确实是product;
int right = (int)(pro%mod);
int left = (int)(pro/mod);
if(left == reverse(right,n)) return (int)(pro%m);
比如这个就是一种思路(123321的左边是123, 右边是321, 右边reverse跟左边相等); 反正其实都差不多.
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.
这个是我没有分析到的一个点: 为什么the left n bits of the 2n bits从大到小就能保证整个的2n-bit的回文也是从大到小;
discussion上面有人对这个算法给出了一个较为复杂的分析:
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.
这个大概看了一下, 属于是比较复杂的了, 有空深入研究一下;
上面的分析的同一个作者写出了一个先搜索n位数的算法, 居然做到了90%的速度:
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;
}
这个题目的一个主要优化, 就是避免了我的遍历, 完成了一个类似branch&bound(剪枝)的优化. 不对, 好像严格来说这个不是剪枝. 这个其实就是把一个搜索问题转换成为一个普通的stream问题; 有点像是greedy;
具体的思路好像也不是特别的神奇, 就是利用上面一段的一个observation:
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.
这个好像不是很懂, 这会儿discussion又挂了, 完全不能理解这个问题他到底是什么思路; 比如11 22 = 242, 这个是2结尾的啊; 或者如果是限定是偶数位的回文: 66 37 = 2442. 不知道他这里到底是什么意思;
这里是他自己给出的解释:
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.
所以他这里还是有一定的assumption的, 比如我们最后找到的回文product一定是偶数位, 而且一定是9开头;
反正大概看看就行了, 不过他这里这个用pq来完成iteration的思路值得学习; 这种pq的思路就可以让iteration不仅限于consider one iterator (iterating variable) at a time的思路了; 比如这里要完成的就是两个operand的乘积排序;
这个是submission最优解:
public class Solution {
private static int[] cache = {9, 987, 123, 597, 677, 1218, 877, 475};
public int largestPalindrome(int n) {
return cache[n - 1];
}
}
看完也是有点无语的, 所以这个题目其实也是因为给了range(这里还是explicit给的, 不像以前是依靠比如int is 32-bit这样的信息implicit给的), 所以实际上说是让你做一个search, 最后就那么点个可能性, 你只要事先找到这个有限的集合就行了;
不过这种做法也是没有什么教育意义, 看看就行了;
但是万一面试的时候碰到了呢?
我大概理解这个算法的思路了, 这个算法比我想象的还要蠢: 对于每一个n值, 其实最后只有一个答案(最大的那一个), 你如果直接让OJ来帮你search, 那最后肯定是超时, 所以这帮人直接在自己的电脑上把这8个答案全都跑出来, 然后扔进去就行了; 这个答案也是蠢的可以了;
不过真正面试的时候, 我觉得想到这样的思路, 然后略带戏谑的说一下, 并不是一件坏事;
其他的一些最优解, 还有在n = 1..4的时候人模狗样的搜索一下, 然后5开始就直接hardcode的, 各种丢人现眼;
Problem Description
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].
Difficulty:Easy
Total Accepted:3.2K
Total Submissions:16.1K
Contributor: arash2012
Companies
yahoo