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.

Description Hints 3 Solution Video 16:25

3260. Find the Largest Palindrome Divisible by K

Hard17.0% acceptance2 companies

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 <= 10⁵
1 <= k <= 9

Asked at 2 companies

Google Amazon

Topics

Hints open one at a time

Hint 1

It must have a solution since we can have all digits equal to k.

Hint 2

Use string dp, store modulus along with length of number currently formed.

Hint 3

Is it possible to solve greedily using divisibility rules?

16:25

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution