3552. Find the Largest Palindrome Divisible by K
My accepted Python solution to LeetCode problem 3552, Find the Largest Palindrome Divisible by K, running in 99ms.
- Difficulty: Hard
- Python
- Runtime 99ms
- Memory 50.1MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 99ms, memory 50.1MB, accepted 2025-12-29.
class Solution:
def largestPalindrome(self, n: int, k: int) -> str:
if k == 1:
return '9' * n
elif k == 2:
if n == 1:
return '8'
elif n == 2:
return '88'
else:
return '8' + '9' * (n - 2) + '8'
elif k == 3 or k == 9:
return '9' * n
elif k == 4:
# Divisibility by 4 depends on last 2 digits
# For palindrome of length n, last 2 digits are result[n-2], result[n-1]
# which equal result[1], result[0] (mirrored)
if n == 1:
return '8'
elif n == 2:
# XY where Y=X, need XX divisible by 4
# 11*X divisible by 4: X=8 gives 88 which is divisible by 4
return '88'
elif n == 3:
# XYX: last 2 digits = YX, need 10Y+X divisible by 4
# For X=8: 10Y+8 mod 4 = 2Y mod 4 = 0, so Y=0,2,4,6,8
# Largest is Y=8, giving 888
return '888'
else:
# For n>=4: XYYZ...ZYX
# Last 2 digits = [n-2][n-1] = [1][0] = YX
# We need 10Y + X divisible by 4
# Want X as large as possible (8), then Y as large as possible
# For X=8: need 2Y mod 4 = 0, so Y=0,2,4,6,8
# Largest Y with this property is 8
# So we use X=8, Y=8, fill rest with 9s
if n == 4:
return '8888'
else:
return '88' + '9' * (n - 4) + '88'
elif k == 5:
if n == 1:
return '5'
elif n == 2:
return '55'
else:
return '5' + '9' * (n - 2) + '5'
elif k == 6:
if n == 1:
return '6'
elif n == 2:
return '66'
else:
if n % 2 == 1:
mid_9s = (n - 3) // 2
base_sum = 16 + 9 * (n - 3)
for mid in range(9, -1, -1):
if (base_sum + mid) % 3 == 0:
return '8' + '9' * mid_9s + str(mid) + '9' * mid_9s + '8'
else:
mid_9s = (n - 4) // 2
base_sum = 16 + 9 * (n - 4)
for mid in range(9, -1, -1):
if (base_sum + 2 * mid) % 3 == 0:
return '8' + '9' * mid_9s + str(mid) * 2 + '9' * mid_9s + '8'
elif k == 7:
half = (n + 1) // 2
pow10 = [1] * n
for i in range(1, n):
pow10[i] = (pow10[i - 1] * 10) % 7
def contrib(pos, d):
if n % 2 == 1 and pos == n // 2:
return (d * pow10[pos]) % 7
else:
return (d * (pow10[n - 1 - pos] + pow10[pos])) % 7
result = [''] * n
def solve(pos, rem):
if pos == half:
return rem == 0
for d in range(9, -1, -1):
if pos == 0 and d == 0 and n > 1:
continue
c = contrib(pos, d)
new_rem = (rem + c) % 7
if solve(pos + 1, new_rem):
result[pos] = str(d)
result[n - 1 - pos] = str(d)
return True
return False
solve(0, 0)
return ''.join(result)
elif k == 8:
if n == 1:
return '8'
elif n == 2:
return '88'
elif n == 3:
for x in range(9, 0, -1):
for y in range(9, -1, -1):
num = x * 100 + y * 10 + x
if num % 8 == 0:
return str(num)
elif n == 4:
for x in range(9, 0, -1):
for y in range(9, -1, -1):
last3 = y * 100 + y * 10 + x
if last3 % 8 == 0:
return str(x) + str(y) * 2 + str(x)
elif n == 5:
for x in range(9, 0, -1):
for y in range(9, -1, -1):
for z in range(9, -1, -1):
last3 = z * 100 + y * 10 + x
if last3 % 8 == 0:
return str(x) + str(y) + str(z) + str(y) + str(x)
else:
for d0 in range(9, 0, -1):
for d1 in range(9, -1, -1):
for d2 in range(9, -1, -1):
last3 = d2 * 100 + d1 * 10 + d0
if last3 % 8 == 0:
if n == 6:
return str(d0) + str(d1) + str(d2) + str(d2) + str(d1) + str(d0)
else:
mid_len = n - 6
return str(d0) + str(d1) + str(d2) + '9' * mid_len + str(d2) + str(d1) + str(d0)
return ""