Find the Largest Palindrome Divisible by K

Find the Largest Palindrome Divisible by K

What is this problem about?

The Find the Largest Palindrome Divisible by K interview question is a difficult number theory and string construction problem. You are given an integer $n$ (the length of the palindrome) and an integer $k$. You need to find the largest $n$-digit palindrome that is divisible by $k$. Because $n$ can be large ($10^5$), you must return the answer as a string.

Why is this asked in interviews?

Amazon and Google ask the Find the Largest Palindrome coding problem to test a candidate's mastery of Greedy algorithms and Dynamic Programming. Since you want the largest number, you should try to put '9's at the most significant positions. However, the divisibility rule for $k$ (especially for $k=7$ or $k=13$) requires a structured approach.

Algorithmic pattern used

This problem is solved using Greedy Construction with DP/Math.

1. Divisibility Rules:

• $k=1, 3, 9$: All '9's work.
• $k=2, 4, 8, 5$: The outer digits (and sometimes those near the center) are constrained (e.g., must be even for $k=2$).
• $k=7$: Requires a more complex check.

1. DP State: dp(index, current_remainder) stores whether it's possible to complete a palindrome starting from index with a given remainder.
2. Greedy Choice: At each position (from outside in), try digits from 9 down to 0. Use the DP table to see if that choice can lead to a remainder of 0 at the end.

Example explanation

$n=3, k=7$.

1. Start from outside: Try 9. "9_9".
2. Remainder of "9_9" modulo 7: $(909 + 10x) \pmod 7$.
3. Try $x=9$: $999 \pmod 7 = 6$.
4. Try $x=8$: $989 \pmod 7 = 2$.
5. Try $x=5$: $959 \pmod 7 = 0$. Result: "959".

Common mistakes candidates make

• Integer Overflow: Trying to use numeric types for a $10^5$ digit number.
• Inefficient Search: Not using DP to prune the search, resulting in an exponential $10^{n/2}$ complexity.
• Incorrect Modulo Math: Failing to handle the "mirrored" contribution of digits to the remainder.

Interview preparation tip

For large-number divisibility, learn how to calculate the remainder of $10^p \pmod k$ iteratively. This allows you to update the total remainder digit-by-digit without ever storing the full number. This is a powerful Number Theory interview pattern.