Watch 4 video solutions for Find the Largest Palindrome Divisible by K, a hard level problem involving Math, String, Dynamic Programming. This walkthrough by Pulkit Malhotra has 1,257 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 9Problem Overview: You are given the number of digits n and an integer k. The task is to construct the largest n-digit palindrome whose numeric value is divisible by k. Since the result can be extremely large, the solution focuses on building the palindrome as a string while controlling the remainder using modular arithmetic.
Approach 1: Reverse Check Starting Approach (Brute Force) (Time: O(10^(n/2) * n), Space: O(n))
Start from the largest possible n-digit palindrome and move downward until you find one divisible by k. A palindrome is defined by its first half, so generate candidates by decreasing the first half and mirroring it to form the full number. For each generated palindrome, compute value % k. If the remainder is zero, you found the answer. This approach is straightforward and demonstrates the brute-force search space, but the number of candidates grows exponentially with n/2, making it impractical for large inputs.
Approach 2: Iterative Palindrome Construction (Greedy + DP on Remainders) (Time: O(n * k * 10), Space: O(n * k))
Instead of checking every palindrome, construct the number digit by digit from the outside toward the center. Each position contributes a weighted value modulo k. Precompute powers of 10 modulo k using number theory. Then use dynamic programming on the remainder state: track whether the remaining positions can still produce a valid total remainder of 0. For each symmetric digit pair, try digits from 9 down to 0 (greedy for the largest result). Choose the largest digit that still allows a valid remainder path according to the DP table. For odd-length palindromes, handle the middle digit separately. This strategy guarantees the lexicographically largest palindrome while maintaining divisibility.
Recommended for interviews: The iterative palindrome construction approach is the one interviewers expect. It combines mod k arithmetic, greedy digit selection, and dynamic programming to prune impossible states. Showing the brute-force palindrome enumeration first demonstrates understanding of the search space, but implementing the remainder-based DP proves you can optimize exponential generation into a controlled O(n * k) state exploration.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Reverse Check Starting Approach | O(10^(n/2) * n) | O(n) | Small n or when demonstrating brute-force palindrome enumeration |
| Iterative Palindrome Construction (Greedy + DP) | O(n * k * 10) | O(n * k) | Large n where direct enumeration is infeasible; optimal interview solution |