LeetCode Problem 3260

Difficulty: 🔴 Hard
Topics: Math, String, Dynamic Programming, Greedy, Number Theory

Solution

LeetCode 3260 - Find the Largest Palindrome Divisible by K

Problem Understanding

The problem asks us to construct the largest possible palindrome with exactly n digits such that the resulting number is divisible by k.

A palindrome is a number that reads the same forward and backward. For example, 595, 1221, and 8 are palindromes. Numbers like 123 or 1201 are not.

We are given:

• n, the required number of digits
• k, the divisor

We must return the lexicographically largest valid palindrome as a string.

The phrase "largest integer" is extremely important. Since all valid answers have exactly n digits, maximizing the numeric value is equivalent to maximizing the digits from left to right. This immediately suggests a greedy strategy: we want the leftmost digits to be as large as possible.

The constraints are the key to understanding what kind of solution is required:

• 1 <= n <= 10^5
• 1 <= k <= 9

The length can be extremely large. A brute force search over all n digit palindromes is completely impossible. Even storing such huge integers in standard numeric types is not feasible for very large n.

Instead, we must work directly with strings and modular arithmetic.

Another important observation is that k is very small, only from 1 to 9. This small divisor is the core reason an efficient dynamic programming solution is possible.

Several edge cases immediately stand out:

• n = 1, where every single digit palindrome is valid
• Very large n, where constructing huge integers directly would overflow
• Cases where the largest all-9 palindrome is not divisible by k
• Odd versus even palindrome lengths
• Situations where the middle digit determines divisibility

The problem guarantees that n and k are positive integers, and because k <= 9, a valid palindrome always exists.

Problem Understanding

The problem asks us to find the largest n-digit integer that is a palindrome and divisible by a given integer k. In other words, we are looking for a number x that meets three conditions: it has exactly n digits, it reads the same forwards and backwards, and it is divisible evenly by k. The output must be returned as a string to preserve leading zeros if necessary, though in this problem, the number is guaranteed to have no leading zeros.

The inputs are two positive integers: n (the number of digits) and k (the divisor). The constraints 1 <= n <= 10^5 and 1 <= k <= 9 indicate that the solution must efficiently handle very large numbers, up to 100,000 digits. This rules out naive enumeration of all n-digit numbers, since iterating through numbers of size 10^100000 is infeasible. The small range of k (1 to 9) suggests divisibility checks can be optimized using modular arithmetic without performing full division on huge integers.

Important edge cases include:

1. n = 1: single-digit palindromes are just the digits themselves, so the largest divisible by k is straightforward.
2. k = 1: every palindrome is divisible by 1, so the largest n-digit palindrome is all 9s.
3. Extremely large n: we cannot construct the full number explicitly using integer arithmetic; string manipulation is required.

Approaches

Brute Force Approach

A brute force solution would generate palindromes in descending order and check divisibility by k.

One possible implementation would:

1. Enumerate the first half of the palindrome from largest to smallest
2. Mirror it to construct the full palindrome
3. Convert the result into an integer
4. Check whether it is divisible by k
5. Return the first valid palindrome found

This works because every palindrome can be uniquely generated from its first half.

However, the number of possible first halves is enormous. For an n digit palindrome, we must explore roughly:

$$10^{\lceil n/2 \rceil}$$

possibilities.

When n = 100000, this is astronomically large and completely infeasible.

Even computing divisibility for all candidates would take far too long.

Key Insight

The important observation is that a palindrome is fully determined by its left half.

Instead of generating every palindrome, we can build the answer digit by digit from left to right.

Suppose we place digit d at positions:

• i
• n - 1 - i

Because the palindrome is symmetric, these two positions contribute together to the final remainder modulo k.

We can precompute powers of 10 modulo k:

$$10^i \bmod k$$

Then each mirrored digit contributes:

$$d \times (10^i + 10^{n-1-i}) \bmod k$$

For the middle digit in odd length palindromes, the contribution appears only once.

This transforms the problem into:

• Constructing the lexicographically largest sequence of mirrored digits
• Such that the final modulo becomes 0

Since k <= 9, there are only at most 9 remainder states.

We can use dynamic programming to determine whether a certain remainder is achievable from a certain position onward.

Then we greedily place the largest valid digit at each step.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	$O(10^{n/2})$	$O(n)$	Enumerates all palindromes
Optimal	$O(n \cdot k \cdot 10)$	$O(n \cdot k)$	DP with greedy palindrome construction

Algorithm Walkthrough

Step 1: Determine How Many Independent Digits Exist

A palindrome is determined entirely by its first half.

If:

• n = 6, positions are paired as (0,5), (1,4), (2,3)
• n = 5, positions are (0,4), (1,3), and middle (2)

So we only need to decide:

$$m = \left\lceil \frac{n}{2} \right\rceil$$

digits.

Step 2: Precompute Powers of 10 Modulo k

We compute:

$$pow10[i] = 10^i \bmod k$$

for all positions.

This allows us to evaluate digit contributions without constructing enormous integers.

Step 3: Compute Contribution of Each Palindrome Position

For each independent position i in the first half:

• If it mirrors another position:

$$contrib[i] = 10^i + 10^{n-1-i}$$

• If it is the middle position of an odd length palindrome:

$$contrib[i] = 10^i$$

All computations are taken modulo k.

This tells us how much placing digit d changes the remainder.

Step 4: Build a DP Table

Define:

$$dp[pos][rem]$$

to mean:

"Starting from position pos, can we complete the palindrome so that the final remainder becomes rem?"

We process positions backward.

Base case:

• At position m, only remainder 0 is valid

Transition:

For every digit d:

$$newRem = (rem + d \times contrib[pos]) \bmod k$$

If the suffix can finish from newRem, then the current state is achievable.

Step 5: Greedily Construct the Largest Palindrome

We now build the answer from left to right.

At each position:

1. Try digits from 9 down to 0
2. Skip leading zero
3. Compute the new remainder
4. Check whether the remaining positions can still achieve divisibility
5. Choose the first valid digit

Because digits are tried from largest to smallest, the resulting palindrome is the maximum possible.

Step 6: Mirror the Left Half

Once the first half is constructed:

• Mirror it to produce the full palindrome
• Handle odd lengths carefully so the center digit is not duplicated

Why it works

The DP guarantees that whenever we choose a digit greedily, the remaining suffix can still produce a divisible palindrome.

Because we always select the largest feasible digit at the earliest position, the final result is lexicographically maximal.

The palindrome property is guaranteed because every chosen digit is mirrored symmetrically.

Divisibility is guaranteed because the DP only permits constructions that end with remainder 0. A brute force approach would generate all n-digit numbers in descending order, check if each is a palindrome, and test if it is divisible by k. This guarantees correctness, as we are checking every candidate in order from largest to smallest. However, this approach is infeasible because the number of n-digit integers grows exponentially with n, reaching up to 10^105 possibilities. Generating and checking each candidate individually is far too slow, especially for large n.

Optimal Approach

The key insight is that palindromes are fully determined by their first half. For an n-digit number, constructing the first ceil(n / 2) digits is sufficient, and the second half is a mirror of the first. Instead of iterating over all numbers, we iterate only over possible first halves in descending order. For each candidate first half, we construct the palindrome and check if it is divisible by k. Because k is small (1-9), we can efficiently compute the remainder using modular arithmetic without constructing the full integer when n is very large. This reduces the search space drastically from 10^n to 10^(ceil(n/2)).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(10^n)	O(1)	Check every n-digit number in descending order, slow for n > 10
Optimal	O(10^(ceil(n/2)))	O(n)	Generate first half of palindrome and mirror, efficient even for n up to 10^5

Algorithm Walkthrough

1. Compute half_len = (n + 1) // 2, which is the number of digits that determine the palindrome.
2. Start from the largest half value of half_len digits (all 9s) and decrement down to the smallest valid first half (e.g., 1 followed by zeros if n > 1).
3. For each half candidate, construct the full palindrome by mirroring the digits. If n is odd, exclude the last digit of the half in the mirrored portion.
4. Compute the remainder of the palindrome modulo k. For large n, do this using modular arithmetic digit by digit to avoid integer overflow.
5. If the remainder is 0, return the palindrome as a string.
6. Continue iterating through half until a valid palindrome divisible by k is found.

Why it works: The largest palindrome is always obtained by starting with the largest first half and mirroring it. Because we iterate in descending order, the first palindrome divisible by k is guaranteed to be the largest possible.

Python Solution

class Solution:
    def largestPalindrome(self, n: int, k: int) -> str:
        half_len = (n + 1) // 2

        pow10 = [1] * n
        for i in range(1, n):
            pow10[i] = (pow10[i - 1] * 10) % k

        contrib = [0] * half_len

        for i in range(half_len):
            left_pos = n - 1 - i
            right_pos = i

            if left_pos == right_pos:
                contrib[i] = pow10[left_pos] % k
            else:
                contrib[i] = (pow10[left_pos] + pow10[right_pos]) % k

        dp = [[False] * k for _ in range(half_len + 1)]
        dp[half_len][0] = True

        for pos in range(half_len - 1, -1, -1):
            for rem in range(k):
                for digit in range(10):
                    new_rem = (rem + digit * contrib[pos]) % k
                    if dp[pos + 1][new_rem]:
                        dp[pos][rem] = True
                        break

        result = []
        current_rem = 0

        for pos in range(half_len):
            start_digit = 1 if pos == 0 else 0

            for digit in range(9, start_digit - 1, -1):
                next_rem = (current_rem + digit * contrib[pos]) % k

                if dp[pos + 1][next_rem]:
                    result.append(str(digit))
                    current_rem = next_rem
                    break

        left_half = "".join(result)

        if n % 2 == 0:
            return left_half + left_half[::-1]
        else:
            return left_half + left_half[:-1][::-1]

The implementation begins by determining how many independent palindrome positions exist. Since the right half is fully determined by the left half, only the first half must be constructed explicitly.

The pow10 array stores powers of ten modulo k. This allows the algorithm to compute divisibility contributions efficiently without constructing huge integers.

The contrib array captures how much each chosen digit contributes to the final remainder. Mirrored positions contribute twice, while the middle digit contributes once.

The DP table is then built from the back toward the front. Each state records whether it is possible to complete the palindrome from that position while achieving a valid remainder.

Finally, the palindrome is constructed greedily. At every position, digits are attempted from 9 downward. The first digit that still allows a valid completion is selected.

The second half of the palindrome is produced by mirroring the constructed first half. if n == 1: for num in range(9, 0, -1): if num % k == 0: return str(num)

    half_len = (n + 1) // 2
    start = int('9' * half_len)
    end = 10 ** (half_len - 1)
    
    for half in range(start, end - 1, -1):
        half_str = str(half)
        if n % 2 == 0:
            pal_str = half_str + half_str[::-1]
        else:
            pal_str = half_str + half_str[:-1][::-1]
        
        # Compute modulo k using digit-wise method to avoid large integers
        remainder = 0
        for ch in pal_str:
            remainder = (remainder * 10 + int(ch)) % k
        
        if remainder == 0:
            return pal_str
    
    return ""  # Should not happen given constraints

**Explanation:** The code first handles the single-digit case. It then constructs the largest possible half, iterates downwards, mirrors to create a full palindrome, and checks divisibility using modular arithmetic to handle very large numbers. Once a divisible palindrome is found, it returns immediately.

## Go Solution

```go
func largestPalindrome(n int, k int) string {
    halfLen := (n + 1) / 2

    pow10 := make([]int, n)
    pow10[0] = 1 % k

    for i := 1; i < n; i++ {
        pow10[i] = (pow10[i-1] * 10) % k
    }

    contrib := make([]int, halfLen)

    for i := 0; i < halfLen; i++ {
        leftPos := n - 1 - i
        rightPos := i

        if leftPos == rightPos {
            contrib[i] = pow10[leftPos] % k
        } else {
            contrib[i] = (pow10[leftPos] + pow10[rightPos]) % k
        }
    }

    dp := make([][]bool, halfLen+1)

    for i := range dp {
        dp[i] = make([]bool, k)
    }

    dp[halfLen][0] = true

    for pos := halfLen - 1; pos >= 0; pos-- {
        for rem := 0; rem < k; rem++ {
            for digit := 0; digit <= 9; digit++ {
                newRem := (rem + digit*contrib[pos]) % k

                if dp[pos+1][newRem] {
                    dp[pos][rem] = true
                    break
                }
            }
        }
    }

    result := make([]byte, 0, halfLen)
    currentRem := 0

    for pos := 0; pos < halfLen; pos++ {
        startDigit := 0
        if pos == 0 {
            startDigit = 1
        }

        for digit := 9; digit >= startDigit; digit-- {
            nextRem := (currentRem + digit*contrib[pos]) % k

            if dp[pos+1][nextRem] {
                result = append(result, byte('0'+digit))
                currentRem = nextRem
                break
            }
        }
    }

    leftHalf := string(result)

    if n%2 == 0 {
        reversed := reverseString(leftHalf)
        return leftHalf + reversed
    }

    reversed := reverseString(leftHalf[:len(leftHalf)-1])
    return leftHalf + reversed
}

func reverseString(s string) string {
    bytes := []byte(s)

    for i, j := 0, len(bytes)-1; i < j; i, j = i+1, j-1 {
        bytes[i], bytes[j] = bytes[j], bytes[i]
    }

    return string(bytes)
}

The Go implementation follows exactly the same logic as the Python version.

Since Go strings are immutable, the palindrome is constructed using a []byte slice for efficiency.

The helper function reverseString reverses the mirrored portion efficiently in place.

Because k <= 9, integer overflow is never a concern for modulo computations.

Worked Examples

Example 1

Input:

n = 3
k = 5

Step 1: Determine Half Length

$$halfLen = 2$$

We only choose the first two digits.

Step 2: Contributions

Position	Mirrored Positions	Contribution Mod 5
0	(0, 2)	1 + 0 = 1
1	(1)	0

Step 3: Greedy Construction

Position	Try Digit	Valid?	Chosen
0	9	No
0	8	No
0	7	No
0	6	No
0	5	Yes	5
1	9	Yes	9

Left half becomes:

59

Mirroring gives:

595

Example 2

Input:

n = 1
k = 4

Only one digit exists.

Digits are tested from 9 downward:

Digit	Divisible by 4?
9	No
8	Yes

Answer:

8

Example 3

Input:

n = 5
k = 6

Half length:

3

Constructed left half:

898

Mirrored palindrome:

89898

Check divisibility:

$$89898 \bmod 6 = 0$$

So the answer is valid. import "strconv"

func largestPalindrome(n int, k int) string { if n == 1 { for num := 9; num >= 1; num-- { if num % k == 0 { return strconv.Itoa(num) } } }

halfLen := (n + 1) / 2
start := 0
for i := 0; i < halfLen; i++ {
    start = start*10 + 9
}
end := 1
for i := 1; i < halfLen; i++ {
    end *= 10
}

for half := start; half >= end; half-- {
    halfStr := strconv.Itoa(half)
    var palStr string
    if n % 2 == 0 {
        palStr = halfStr + reverse(halfStr)
    } else {
        palStr = halfStr + reverse(halfStr[:len(halfStr)-1])
    }
    
    remainder := 0
    for i := 0; i < len(palStr); i++ {
        remainder = (remainder*10 + int(palStr[i]-'0')) % k
    }
    
    if remainder == 0 {
        return palStr
    }
}

return ""

}

func reverse(s string) string { runes := []rune(s) for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 { runes[i], runes[j] = runes[j], runes[i] } return string(runes) }

**Explanation:** The Go version mirrors the Python logic, using string manipulation and modular arithmetic to handle large numbers. `strconv` is used for integer-to-string conversion, and a helper `reverse` function mirrors the half string. Modulo calculations are done digit by digit to avoid overflow.

## Worked Examples

**Example 1:** n = 3, k = 5

| Step | half | pal_str | remainder | divisible? |
| --- | --- | --- | --- | --- |
| 1 | 999 | 999 | 4 | no |
| 2 | 998 | 998 | 3 | no |
| 3 | 995 | 595 | 0 | yes |

Output: `"595"`

**Example 2:** n = 1, k = 4

Check digits 9 → 1: 8 is divisible by 4, output `"8"`.

**Example 3:** n = 5, k = 6

Start half = 999 → pal = 99999 → rem = 3, continue down until half = 898 → pal = 89898 → rem = 0.

Output: `"89898"`

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | $O(n \cdot k \cdot 10)$ | Each position processes all remainders and digits |
| Space | $O(n \cdot k)$ | DP table storage |

Since `k <= 9`, the complexity is effectively linear in `n`.

The algorithm easily handles `n = 100000` because the DP state space remains tiny.
| Time | O(10^(ceil(n/2))) | Only generate first half of palindrome and mirror, checking modulo k per candidate |
| Space | O(n) | Store the palindrome as a string of length n |

The key optimization is halving the search space by generating only half the digits. Modulo computation avoids integer overflow, keeping memory usage linear in the number of digits.

## Test Cases

sol = Solution()

assert sol.largestPalindrome(3, 5) == "595" # provided example assert sol.largestPalindrome(1, 4) == "8" # single digit case assert sol.largestPalindrome(5, 6) == "89898" # provided example

assert sol.largestPalindrome(1, 1) == "9" # any number divisible by 1 assert sol.largestPalindrome(2, 2) == "88" # largest even divisible palindrome assert sol.largestPalindrome(2, 5) == "55" # divisible by 5 requires ending in 5 assert sol.largestPalindrome(4, 3) == "9999" # sum of digits divisible by 3 assert sol.largestPalindrome(6, 7) == "999999" # large repeated digits assert sol.largestPalindrome(7, 8) == "8889888" # divisibility by 8 assert sol.largestPalindrome(10, 9) == "9999999999" # large divisible by 9 assert len(sol.largestPalindrome(100000, 3)) == 100000 # stress test

## Test Summary

| Test | Why |
| --- | --- |
| `(3, 5)` | Validates sample case |
| `(1, 4)` | Tests single digit palindrome |
| `(5, 6)` | Tests odd length construction |
| `(1, 1)` | Every number divisible by 1 |
| `(2, 2)` | Even divisibility requirement |
| `(2, 5)` | Checks divisibility by 5 |
| `(4, 3)` | Digit sum divisibility |
| `(6, 7)` | Nontrivial modulo behavior |
| `(7, 8)` | Odd length with divisibility by 8 |
| `(10, 9)` | Large repeated digits |
| `(100000, 3)` | Maximum constraint stress test |

## Edge Cases

### Single Digit Palindromes

When `n = 1`, the palindrome consists of only one digit. There are no mirrored positions, and the algorithm must avoid incorrectly duplicating digits during reconstruction.

The implementation handles this naturally because the half length becomes `1`, and the mirroring logic for odd lengths correctly avoids duplicating the center digit.

### Leading Zero Problems

A naive palindrome generator might accidentally place `0` in the first position, creating a number with fewer than `n` digits.

The implementation explicitly prevents this by forcing the first chosen digit to start from `1` instead of `0`.

### Odd Length Middle Digit

Odd length palindromes contain a center digit that should contribute only once to the modulo calculation.

This is easy to mishandle if every position is assumed to have a mirrored counterpart.

The implementation correctly detects the middle position and uses only a single power-of-ten contribution.

### Very Large n

When `n` reaches `100000`, constructing or converting integers directly would overflow and become extremely slow.

The implementation never constructs numeric integers. All arithmetic is performed modulo `k`, and the palindrome itself is maintained as a string, making the solution scalable to the maximum constraint.
# Basic examples
assert Solution().largestPalindrome(3, 5) == "595"  # Example 1
assert Solution().largestPalindrome(1, 4) == "8"    # Example 2
assert Solution().largestPalindrome(5, 6) == "89898" # Example 3

# Edge cases
assert Solution().largestPalindrome(1, 1) == "9"    # largest 1-digit divisible by 1
assert Solution().largestPalindrome(2, 9) == "99"   # 2-digit largest divisible by 9
assert Solution().largestPalindrome(6, 2) == "999999" # even n divisible by 2
``