Largest palindrome product: Difference between revisions
→{{header|Julia}}
m (cleanup) |
|||
Line 477:
For factor length 11, 99999943851 * 99999996349 = 9999994020000204999999
For factor length 12, 999999000001 * 999999999999 = 999999000000000000999999
</pre>
=== Faster version ===
{{trans|Python}}
<lang julia>""" taken from https://leetcode.com/problems/largest-palindrome-product/discuss/150954/Fast-algorithm-by-constrains-on-tail-digits """
const T = [Set([(0, 0)])]
function double(it)
arr = empty(it)
for p in it
push!(arr, p, reverse(p))
end
return arr
end
""" Construct a pair of n-digit numbers such that their product ends with 99...9 pattern """
function tails(n)
if length(T) <= n
l = Set()
for i in 0:9, j in i:9
I = i * 10^(n-1)
J = j * 10^(n-1)
it = collect(tails(n - 1))
I != J && (it = double(it))
for (t1, t2) in it
if ((I + t1) * (J + t2) + 1) % 10^n == 0
push!(l, (I + t1, J + t2))
end
end
end
push!(T, l)
end
return T[n + 1]
end
""" find the largest palindrome that is a product of n-digit numbers """
function largestpalindrome(n)
m, tail = 0, n ÷ 2
head = n - tail
up = 10^head
for L in 1 : 9 * 10^(head-1)
# Consider small shell (up-L)^2 < (up-i)*(up-j) <= (up-L)^2, 1<=i<=L<=j
m, sol = 0, (0, 0)
for i in 1:L
lo = max(i, BigInt(up - (up - L + 1)^2 ÷ (up - i)) + 1)
hi = BigInt(up - (up - L)^2 ÷ (up - i))
for j in lo:hi
I = (up - i) * 10^tail
J = (up - j) * 10^tail
it = collect(tails(tail))
I != J && (it = double(it))
for (t1, t2) in it
val = (I + t1) * (J + t2)
s = string(val)
if s == reverse(s) && val > m
sol = (I + t1, J + t2)
m = val
end
end
end
end
if m > 0
println(lpad(n, 2), " ", lpad(m % 1337, 4), " $sol $(sol[1] * sol[2])")
return m % 1337
end
end
return 0
end
for k in 1:16
largestpalindrome(k)
end
</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
14 959 (99999990000001, 99999999999999) 9999999000000000000009999999
15 465 (999999998341069, 999999975838971) 999999974180040040081479999999
16 51 (9999999900000001, 9999999999999999) 99999999000000000000000099999999
</pre>
| |||