Scale Engineer

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
MathDynamic ProgrammingGreedyNumber 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 <= 105
  • 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:

  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.
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 "";     }}

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.

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 →

Next problem