Skip to main content
Talentd

Find the Largest Palindrome Divisible by K - Solution & Explanation

HardMathStringDynamic ProgrammingGreedy7 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

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 <= 105
  • 1 <= k <= 9

Approach Overview

Problem 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 1: Iterative Palindrome Construction

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.

Code

PythonC++JavaJavaScript

Python

C++

Java

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Reverse Check Starting Approach

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.

Code

CC#

C

C#

Complexity

Time Complexity: O(10^(n/2)).
Space Complexity: O(1).

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative Palindrome Construction

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.

Reverse Check Starting Approach

Time Complexity: O(10^(n/2)).
Space Complexity: O(1).

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Reverse Check Starting ApproachO(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

Video Solution

3260. Find the Largest Palindrome Divisible by K | Weekly Contest 411 | LeetCode • Pulkit Malhotra • 1,282 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Find the Largest Palindrome Divisible by K easy or hard?
Find the Largest Palindrome Divisible by K is categorized as a Hard problem. The challenge comes from combining palindrome constraints with divisibility checks while avoiding large integer arithmetic, requiring dynamic programming with modular math.
Find the Largest Palindrome Divisible by K Python/Java solution
Most implementations construct the palindrome using a greedy loop and remainder DP. Python uses lists or strings for building the result, while Java or C++ often use character arrays. The logic remains the same: track modulo contributions and choose the largest valid digit at each step.
How to solve Find the Largest Palindrome Divisible by K in O(n)?
Pure O(n) is generally not achievable because the algorithm must consider remainder states modulo k. The practical optimal solution is O(n * k * 10), where you precompute powers of 10 modulo k and use DP to determine whether remaining positions can achieve remainder 0. Greedy digit selection ensures the final palindrome is the largest.
What is the best approach for Find the Largest Palindrome Divisible by K?
The most efficient approach builds the palindrome digit by digit while tracking remainders modulo k. Using greedy selection (try digits from 9 down to 0) combined with dynamic programming on remainder states ensures the largest possible palindrome is constructed. This method runs in O(n * k * 10) time and avoids enumerating all palindromes.
Is Find the Largest Palindrome Divisible by K asked at Google/Amazon/Meta?
Problems combining palindrome construction with modular arithmetic and greedy digit selection frequently appear in interviews at companies like Google, Amazon, and Meta. They test understanding of number theory, remainder propagation, and building large numbers without integer overflow.
What data structure is used in Find the Largest Palindrome Divisible by K?
The solution mainly uses strings or character arrays to construct the palindrome and a dynamic programming table that tracks reachable remainders modulo k. Precomputed arrays for powers of 10 modulo k are also used to calculate digit contributions efficiently.
What is the time complexity of Find the Largest Palindrome Divisible by K?
The optimized greedy + DP approach runs in O(n * k * 10) time and O(n * k) space because each position in the palindrome evaluates up to 10 digit choices while tracking k possible remainders. A brute-force enumeration approach can take O(10^(n/2) * n) time since it generates and checks many palindromes.

Ready to solve this problem?

Practice Find the Largest Palindrome Divisible by K with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find the Closest Palindrome

Next

Palindrome Number