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.
This approach involves starting from the largest n-digit number and iteratively constructing a palindrome while checking for divisibility by k. For even-digit palindromes, half the digits determine the rest, while for odd digits, one central digit can vary. Generate such numbers and check if they meet the conditions.
This Python function starts from the largest n-digit number and decrements until it finds a number that is both palindrome and divisible by k. It checks for palindromic property by comparing the string to its reverse.
Python
C++
Java
JavaScript
Time Complexity: O(9 * 10^(n/2)), since we mostly check half the digits.
Space Complexity: O(1), aside from auxiliary storage for the palindrome check.
This approach reverses the order of searching to construct the palindrome first and then check for divisibility. It can be more efficient in some cases where palindrome properties dictate prior elimination of candidates.
In this C code, we separately generate the palindrome using the concept of 'half mirror', creating the second half of the number by reversing the first half. Then it checks if the constructed palindrome is divisible by k.
Time Complexity: O(10^(n/2)).
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Iterative Palindrome Construction | Time Complexity: O(9 * 10^(n/2)), since we mostly check half the digits. |
| Reverse Check Starting Approach | Time Complexity: O(10^(n/2)). |
| 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 |
3260. Find the Largest Palindrome Divisible by K | Weekly Contest 411 | LeetCode • Pulkit Malhotra • 1,257 views views
Watch 3 more video solutions →Practice Find the Largest Palindrome Divisible by K with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor