# Find the Largest Palindrome Divisible by K **Difficulty:** HARD [External](https://leetcode.com/problems/find-the-largest-palindrome-divisible-by-k) Canonical: https://scaleengineer.com/dsa/problems/find-the-largest-palindrome-divisible-by-k **Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory) **Data structures:** String --- ## Problem 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` # Approaches ## Brute-Force by Iterating First Halves 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. **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. **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. ### Explanation 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: 1. The length of the first half is `m = (n + 1) / 2`. 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). 3. We iterate a number `i` from `10^m - 1` down to `10^(m-1)`. 4. 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). 5. 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`). 6. The first number `i` that generates a palindrome divisible by `k` gives us the largest such palindrome, so we can return it immediately. ```java import java.math.BigInteger; class Solution { public String largestKPalindromic(int n, int k) { int halfLen = (n + 1) / 2; // The problem constraints ensure n>=1, so halfLen-1 >= 0 BigInteger start = BigInteger.TEN.pow(halfLen - 1); BigInteger end = BigInteger.TEN.pow(halfLen).subtract(BigInteger.ONE); BigInteger bigK = BigInteger.valueOf(k); for (BigInteger i = end; i.compareTo(start) >= 0; i = i.subtract(BigInteger.ONE)) { String firstHalf = i.toString(); StringBuilder secondHalfBuilder = new StringBuilder(firstHalf).reverse(); String palindromeStr; if (n % 2 == 1) { palindromeStr = firstHalf + secondHalfBuilder.substring(1); } else { palindromeStr = firstHalf + secondHalfBuilder.toString(); } BigInteger palindromeNum = new BigInteger(palindromeStr); if (palindromeNum.mod(bigK).equals(BigInteger.ZERO)) { return palindromeStr; } } // According to problem constraints, a solution always exists. // This part of the code should be unreachable. return ""; } } ``` ### 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. ## Dynamic Programming on Digits 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`. **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. **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. ### Explanation 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. ```java class Solution { private int n; private int k; private int m; private int[] W; private int[][] memo; private int[][] path; public String largestKPalindromic(int n, int k) { this.n = n; this.k = k; this.m = (n + 1) / 2; W = new int[m]; int[] pow10 = new int[n + 1]; pow10[0] = 1 % k; for (int i = 1; i <= n; i++) { pow10[i] = (pow10[i - 1] * 10) % k; } for (int i = 0; i < m; i++) { if (n % 2 == 1 && i == m - 1) { // Middle digit for odd n W[i] = pow10[i]; } else { W[i] = (pow10[i] + pow10[n - 1 - i]) % k; } } memo = new int[m + 1][k]; // 0: uncomputed, 1: true, -1: false path = new int[m][k]; solve(0, 0); StringBuilder firstHalf = new StringBuilder(); int currentRem = 0; for (int i = 0; i < m; i++) { int digit = path[i][currentRem]; firstHalf.append(digit); currentRem = (currentRem + (int)((long)digit * W[i] % k) + k) % k; } String firstHalfStr = firstHalf.toString(); if (firstHalfStr.length() > 0 && firstHalfStr.charAt(0) == '0') { // This case implies no positive solution was found, which shouldn't happen. // A single '0' is a valid 1-digit palindrome divisible by any k. // But problem asks for largest, and positive solutions exist. return "0"; } StringBuilder secondHalf = new StringBuilder(firstHalfStr).reverse(); if (n % 2 == 1) { return firstHalfStr + secondHalf.substring(1); } else { return firstHalfStr + secondHalf.toString(); } } private boolean solve(int idx, int rem) { if (idx == m) { return rem == 0; } if (memo[idx][rem] != 0) { return memo[idx][rem] == 1; } for (int d = 9; d >= 0; d--) { if (idx == 0 && n > 1 && d == 0) continue; // No leading zeros int newRem = (rem + (int)((long)d * W[idx] % k) + k) % k; if (solve(idx + 1, newRem)) { memo[idx][rem] = 1; path[idx][rem] = d; return true; } } memo[idx][rem] = -1; return false; } } ``` ### 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.