Find the Largest Palindrome Divisible by K

Start by recognizing that palindromes can be constructed digit by digit using a state transition approach. Iterate from the largest possible n-digit number downward while applying modular checks for divisibility by k. Dynamic programming helps track valid prefixes to build the largest k-palindromic integer without redundant recalculations, ensuring efficiency even for large n.

Problem Statement

Given two positive integers n and k, your task is to determine the largest integer with exactly n digits that is divisible by k and forms a palindrome. An integer is considered k-palindromic if it remains divisible by k when considered as a whole number.

Return this largest k-palindromic integer as a string. For instance, for n = 3 and k = 5, the correct output is "595" because it is the largest 3-digit number divisible by 5 that reads the same forwards and backwards.

Examples

Example 1

Input: n = 3, k = 5

Output: "595"

595 is the largest k-palindromic integer with 3 digits.

Example 2

Input: n = 1, k = 4

Output: "8"

4 and 8 are the only k-palindromic integers with 1 digit.

Example 3

Input: n = 5, k = 6

Output: "89898"

Example details omitted.

Constraints

• 1 <= n <= 105
• 1 <= k <= 9

Solution Approach

Construct Palindrome Digit by Digit

Use a state transition dynamic programming table to store remainders for each prefix of the palindrome. Build the number from the highest digit to the center while keeping track of modulus with k to ensure divisibility. This approach avoids generating all numbers explicitly and directly targets valid k-palindromic candidates.

Iterate from Largest Candidates

Start with the largest n-digit numbers and try possible symmetric halves to form palindromes. For each half, compute the complete number and check divisibility by k. This greedy strategy combined with DP allows early pruning of infeasible paths.

Optimize Using Remainder Tracking

Maintain modular arithmetic for each partially constructed palindrome to avoid recalculating the full number each time. This reduces time complexity and ensures the solution scales up to n = 105. Only store remainders that can lead to valid k-palindromic results.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time and space complexity depend on n and k. With remainder tracking and DP, time is O(n * k) and space is O(n * k) in the worst case. Simple brute force is infeasible due to large n, highlighting the need for state transition optimization.

What Interviewers Usually Probe

• Check if you can construct the palindrome from halves rather than brute force.
• Watch for handling the modulo of partially built numbers.
• Consider state transitions to prune invalid prefixes efficiently.

Common Pitfalls or Variants

Common pitfalls

• Failing to account for leading zeros when building palindromes.
• Recalculating full numbers instead of using remainder DP, causing TLE.
• Ignoring symmetric digit placement leading to non-palindromic candidates.

Follow-up variants

• Find the smallest n-digit palindrome divisible by k.
• Return all n-digit palindromes divisible by k.
• Determine the largest palindrome divisible by k within a range of n values.

FAQ

What is a k-palindromic number in this problem?

A k-palindromic number is a palindrome integer divisible by k. The problem focuses on finding the largest n-digit one.

Why is state transition dynamic programming needed here?

DP tracks prefixes and their remainders modulo k to avoid recomputing divisibility for every candidate number.

Can leading zeros appear in the palindrome?

No, the number must have exactly n digits with the first digit non-zero to form a valid n-digit integer.

What if multiple palindromes share the same maximum value?

Only the largest n-digit k-palindromic number needs to be returned, so ties are resolved naturally by construction order.

How does GhostInterview handle n up to 105 efficiently?

It uses remainder tracking and DP to build the palindrome without generating every number explicitly, keeping memory and time manageable.