Find the Largest Palindrome Divisible by K

Hard

#2894Time: O(10^(n/2) * n). The loop runs approximately `9 * 10^((n/2)-1)` times. Inside the loop, creating and checking a palindrome of length `n` takes `O(n)` time with `BigInteger` operations.Space: O(n) to store the palindrome string and the `BigInteger` representation.

Patterns

Math Dynamic Programming Greedy Number Theory

Data structures

String

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves generating all possible n-digit palindromes in descending order and checking for divisibility by k. A palindrome is defined by its first half. We can iterate through all possible first halves from largest to smallest, construct the full palindrome, and the first one that is divisible by k will be our answer. This method is straightforward but computationally expensive.

Algorithm

Calculate the length of the first half of the palindrome, m = (n + 1) / 2.
Define the search range for the first half: from 10^m - 1 down to 10^(m-1).
Iterate through each number i in this range in descending order.
For each i, convert it to its string representation s.
Construct the full palindrome string p_str by concatenating s with the appropriate part of its reverse.
Convert p_str to a BigInteger.
Check if the BigInteger is divisible by k.
If it is, return p_str as it is the largest possible solution.

Walkthrough

The core idea is that an n-digit palindrome is uniquely determined by its first ceil(n/2) digits. Let's call this the "first half". To find the largest palindrome, we should start with the largest possible first half and work our way down.

The algorithm proceeds as follows:

The length of the first half is m = (n + 1) / 2.
The largest number with m digits is 10^m - 1. The smallest is 10^(m-1) (to avoid leading zeros in the final palindrome).
We iterate a number i from 10^m - 1 down to 10^(m-1).
For each i, we construct the full palindrome. If i as a string is s, the palindrome is s + reverse(s) (with the middle digit of s not repeated if n is odd).
Since n can be up to 10^5, the resulting palindrome can be very large. We must use a BigInteger to handle the number and its divisibility check (palindrome.mod(k) == 0).
The first number i that generates a palindrome divisible by k gives us the largest such palindrome, so we can return it immediately.

1import java.math.BigInteger;2 3class Solution {4    public String largestKPalindromic(int n, int k) {5        int halfLen = (n + 1) / 2;6        // The problem constraints ensure n>=1, so halfLen-1 >= 07        BigInteger start = BigInteger.TEN.pow(halfLen - 1);8        BigInteger end = BigInteger.TEN.pow(halfLen).subtract(BigInteger.ONE);9        BigInteger bigK = BigInteger.valueOf(k);10 11        for (BigInteger i = end; i.compareTo(start) >= 0; i = i.subtract(BigInteger.ONE)) {12            String firstHalf = i.toString();13            StringBuilder secondHalfBuilder = new StringBuilder(firstHalf).reverse();14            15            String palindromeStr;16            if (n % 2 == 1) {17                palindromeStr = firstHalf + secondHalfBuilder.substring(1);18            } else {19                palindromeStr = firstHalf + secondHalfBuilder.toString();20            }21 22            BigInteger palindromeNum = new BigInteger(palindromeStr);23            if (palindromeNum.mod(bigK).equals(BigInteger.ZERO)) {24                return palindromeStr;25            }26        }27        28        // According to problem constraints, a solution always exists.29        // This part of the code should be unreachable.30        return ""; 31    }32}

Complexity

Time

O(10^(n/2) * n). The loop runs approximately `9 * 10^((n/2)-1)` times. Inside the loop, creating and checking a palindrome of length `n` takes `O(n)` time with `BigInteger` operations.

Space

O(n) to store the palindrome string and the `BigInteger` representation.

Trade-offs

Pros

Simple to understand and implement.

Cons

Extremely inefficient due to its exponential time complexity.
Times out for values of n greater than approximately 15.

A highly efficient approach is to construct the first half of the palindrome digit by digit, from left to right (most significant to least significant). We can use dynamic programming with memoization to find the largest possible first half that results in a full palindrome divisible by k.

Algorithm

Precompute the weights W_i for each digit h_i of the first half. This requires precomputing powers of 10 modulo k.
Define a recursive function solve(idx, rem) that returns true if a valid suffix for the first half (from idx to m-1) can be formed, given the current remainder rem.
The recursion's base case is idx == m. It returns true if rem == 0, false otherwise.
In solve(idx, rem), iterate through possible digits d from 9 down to 0. The first digit (idx=0) cannot be 0.
For each d, calculate the new_rem = (rem + d * W[idx]) % k and recursively call solve(idx + 1, new_rem).
If the recursive call is successful, it means d is the largest possible digit for this position. Store d and return true.
Use a 2D array memo[idx][rem] for memoization to store the results of solve.
After the main call solve(0, 0) completes, reconstruct the first half string by backtracking through the stored choices.
Construct the full palindrome from the first half.

Walkthrough

The palindrome P can be expressed as a weighted sum of the digits h_0, h_1, ..., h_{m-1} of its first half: P = sum(h_i * W_i), where m = (n+1)/2. The weight W_i for digit h_i depends on its position. For a pair of digits (d_{n-1-i}, d_i), where d_{n-1-i} = d_i = h_i, the weight is W_i = 10^{n-1-i} + 10^i. For the middle digit in an odd-length palindrome, the weight is just its positional value 10^{m-1}.

We need P % k == 0, which translates to (sum(h_i * W_i)) % k == 0.

We can define a recursive function solve(idx, rem) that tries to build the suffix of the first half from index idx onwards, given that the prefix has accumulated a remainder rem modulo k. To find the largest palindrome, for each position idx, we try digits d from 9 down to 0. We greedily pick the first (largest) d for which solve(idx + 1, new_rem) returns true. We use a memoization table memo[idx][rem] to store the results of subproblems to avoid recomputation. A separate table path[idx][rem] can store the chosen digit d to reconstruct the solution.

1class Solution {2    private int n;3    private int k;4    private int m;5    private int[] W;6    private int[][] memo;7    private int[][] path;8 9    public String largestKPalindromic(int n, int k) {10        this.n = n;11        this.k = k;12        this.m = (n + 1) / 2;13 14        W = new int[m];15        int[] pow10 = new int[n + 1];16        pow10[0] = 1 % k;17        for (int i = 1; i <= n; i++) {18            pow10[i] = (pow10[i - 1] * 10) % k;19        }20 21        for (int i = 0; i < m; i++) {22            if (n % 2 == 1 && i == m - 1) { // Middle digit for odd n23                W[i] = pow10[i];24            } else {25                W[i] = (pow10[i] + pow10[n - 1 - i]) % k;26            }27        }28        29        memo = new int[m + 1][k]; // 0: uncomputed, 1: true, -1: false30        path = new int[m][k];31 32        solve(0, 0);33 34        StringBuilder firstHalf = new StringBuilder();35        int currentRem = 0;36        for (int i = 0; i < m; i++) {37            int digit = path[i][currentRem];38            firstHalf.append(digit);39            currentRem = (currentRem + (int)((long)digit * W[i] % k) + k) % k;40        }41 42        String firstHalfStr = firstHalf.toString();43        if (firstHalfStr.length() > 0 && firstHalfStr.charAt(0) == '0') {44             // This case implies no positive solution was found, which shouldn't happen.45             // A single '0' is a valid 1-digit palindrome divisible by any k.46             // But problem asks for largest, and positive solutions exist.47             return "0";48        }49 50        StringBuilder secondHalf = new StringBuilder(firstHalfStr).reverse();51        if (n % 2 == 1) {52            return firstHalfStr + secondHalf.substring(1);53        } else {54            return firstHalfStr + secondHalf.toString();55        }56    }57 58    private boolean solve(int idx, int rem) {59        if (idx == m) {60            return rem == 0;61        }62        if (memo[idx][rem] != 0) {63            return memo[idx][rem] == 1;64        }65 66        for (int d = 9; d >= 0; d--) {67            if (idx == 0 && n > 1 && d == 0) continue; // No leading zeros68 69            int newRem = (rem + (int)((long)d * W[idx] % k) + k) % k;70            if (solve(idx + 1, newRem)) {71                memo[idx][rem] = 1;72                path[idx][rem] = d;73                return true;74            }75        }76 77        memo[idx][rem] = -1;78        return false;79    }80}

Complexity

Time

O(n * k). The number of DP states is `m * k`, which is `O(n*k)`. Each state takes `O(1)` time to compute due to the constant-size loop (10 digits). Precomputation of weights takes `O(n)`.

Space

O(n * k) for the memoization and path tables.

Trade-offs

Pros

Highly efficient with linear time complexity in n.
Guaranteed to find the optimal solution for large constraints.

Cons

More complex to understand and implement compared to brute-force.
Requires more memory to store the DP tables.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem