Largest palindrome product: Difference between revisions
Python example
m (→{{header|Phix}}: added online link) |
(Python example) |
||
Line 663:
Largest palindromic product of two 15-digit integers: 999999974180040040081479999999 = 999999998341069 x 999999975838971 (1 minute and 12s)
Largest palindromic product of two 16-digit integers: 99999999000000000000000099999999 = 9999999999999999 x 9999999900000001 (0s)
</pre>
=={{header|Python}}==
Original author credit to user peijunz at Leetcode.
<lang python>""" taken from https://leetcode.com/problems/largest-palindrome-product/discuss/150954/Fast-algorithm-by-constrains-on-tail-digits """
T=[set([(0, 0)])]
def double(it):
for a, b in it:
yield a, b
yield b, a
def tails(n):
'''Construct pair of n-digit numbers that their product ends with 99...9 pattern'''
if len(T)<=n:
l = set()
for i in range(10):
for j in range(i, 10):
I = i*10**(n-1)
J = j*10**(n-1)
it = tails(n-1)
if I!=J: it = double(it)
for t1, t2 in it:
if ((I+t1)*(J+t2)+1)%10**n == 0:
l.add((I+t1, J+t2))
T.append(l)
return T[n]
def largestPalindrome(n):
"""
:type n: int
:rtype: int
"""
m, tail = 0, n // 2
head = n - tail
up = 10**head
for L in range(1, 9*10**(head-1)+1):
# Consider small shell (up-L)^2 < (up-i)*(up-j) <= (up-L)^2, 1<=i<=L<=j
m = 0
sol = None
for i in range(1, L + 1):
lo = max(i, int(up - (up - L + 1)**2 / (up - i)) + 1)
hi = int(up - (up - L)**2 / (up - i))
for j in range(lo, hi + 1):
I = (up-i) * 10**tail
J = (up-j) * 10**tail
it = tails(tail)
if I!=J: it = double(it)
peijunz for t1, t2 in it:
val = (I + t1)*(J + t2)
s = str(val)
if s == s[::-1] and val>m:
sol = (I + t1, J + t2)
m = val
if m:
print("{:2d}\t{:4d}".format(n, m % 1337), sol, sol[0] * sol[1])
return m % 1337
if __name__ == "__main__":
for k in range(1, 14):
largestPalindrome(k)
</lang>{{out}}
<pre>
1 9 (9, 1) 9
2 987 (91, 99) 9009
3 123 (993, 913) 906609
4 597 (9901, 9999) 99000099
5 677 (99979, 99681) 9966006699
6 1218 (999001, 999999) 999000000999
7 877 (9998017, 9997647) 99956644665999
8 475 (99990001, 99999999) 9999000000009999
9 1226 (999980347, 999920317) 999900665566009999
10 875 (9999986701, 9999996699) 99999834000043899999
11 108 (99999943851, 99999996349) 9999994020000204999999
12 378 (999999000001, 999999999999) 999999000000000000999999
13 1097 (9999999993349, 9999996340851) 99999963342000024336999999
</pre>
| |||