You are given two positive integers n and k.
An integer x is called k-palindromic if:
x is a palindrome.x is divisible by k.Return the largest integer having n digits (as a string) that is k-palindromic.
Note that the integer must not have leading zeros.
Example 1:
Input: n = 3, k = 5
Output: "595"
Explanation:
595 is the largest k-palindromic integer with 3 digits.
Example 2:
Input: n = 1, k = 4
Output: "8"
Explanation:
4 and 8 are the only k-palindromic integers with 1 digit.
Example 3:
Input: n = 5, k = 6
Output: "89898"
Constraints:
1 <= n <= 1051 <= k <= 9In #3260 Find the Largest Palindrome Divisible by K, the goal is to construct the largest numeric palindrome that is divisible by a given integer k. Because palindromes mirror around the center, you only need to decide the first half of the digits and then reflect them to build the full number. This greatly reduces the search space.
A common strategy combines greedy construction with dynamic programming on remainders. While building the palindrome from the most significant digits, you track the remainder of the partially constructed number modulo k. Precomputing powers of 10 modulo k helps determine how each digit contributes to the final remainder. DP or memoization can be used to check whether a valid completion exists for a chosen prefix.
The greedy step attempts larger digits first to ensure the final palindrome is maximized, while the DP ensures divisibility constraints are satisfied. This combination keeps the search efficient and avoids brute-force generation of all palindromes.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy + DP on remainder states | O(n * k * 10) | O(n * k) |
| Palindrome construction with modular arithmetic | O(n * k) | O(k) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
It must have a solution since we can have all digits equal to <code>k</code>.
Use string dp, store modulus along with length of number currently formed.
Is it possible to solve greedily using divisibility rules?
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
While this exact problem may not appear frequently, similar problems involving palindromes, modular arithmetic, and greedy + DP combinations are common in FAANG-style interviews. Practicing it strengthens skills in number theory and state-based optimization.
The optimal approach typically combines greedy digit selection with dynamic programming on modulo states. By constructing the palindrome from the outer digits inward and tracking the remainder modulo k, you can ensure divisibility while maximizing the number.
Dynamic programming helps track whether a partially built palindrome can still lead to a valid number divisible by k. By storing states based on position and remainder, you avoid recomputing possibilities and prune invalid branches early.
Arrays or hash maps are commonly used to store DP states representing positions and remainders. Strings or character arrays are used to build and mirror the palindrome efficiently during construction.