LeetCode Solutions Blog

Find the Largest Palindrome Divisible by K

Number: 3552

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given two positive integers n and k, find the largest n‑digit integer (returned as a string) that is both a palindrome and divisible by k. The palindrome must not have leading zeros.

Key Insights

A palindrome of n digits is determined completely by its first half (and the middle digit if n is odd).
For even n, if we denote the first half as a string a, the full palindrome is formed as a + reverse(a). For odd n, if a is the first half (including the middle digit), the full palindrome is a[0:len(a)-1] + reverse(a).
We need to ensure that the constructed n‑digit palindrome, when interpreted as an integer, is divisible by k.
Since k is small (1 ≤ k ≤ 9) we can use modular arithmetic in our DP state.
A greedy–DP (backtracking) approach is used: process the “controlling” half digit by digit in descending order (from the most significant digit) and choose the highest possible digit at each step that can still lead to a solution.

Space and Time Complexity

Time Complexity: O(n * k * 10) in the worst case, since we fill about ceil(n/2) positions with 10 choices each and our DP state has at most O(n * k) states. Space Complexity: O(n * k) for the DP memoization table and O(n) for storing the resulting palindrome.

Solution

We observe that any n-digit palindrome is completely determined by its first half (if n is even) or the first half including the middle digit (if n is odd). Therefore we define: • L = n/2 for even n, and L = n//2 for the “left part” plus one extra digit (the middle) for odd n. • For each of the positions in the “controlling” half, the digit we choose contributes twice (once for its original place and once for its mirror) except for the middle digit when n is odd, which contributes only once. • We precompute the modular weight of each chosen digit position using the fact that for a digit placed at index i (0-indexed from the left in the full n‑digit palindrome) its contribution is digit * 10^(n-i-1) mod k. In the symmetric positions the contributions sum up. • With the modular weights computed for each “decision position” the problem reduces to picking digits (using DP/backtracking with memoization) for these positions so that the total contribution (mod k) equals 0. • A greedy approach is applied: at each position, try to assign the largest valid digit (taking care to avoid 0 at the first position) and check (via recursion with memoization) if a solution can be found for the remaining positions for the required remainder. • Finally, using the chosen half we mirror it appropriately (excluding the middle digit for odd n) to obtain the full palindrome.

Code Solutions

# Python solution with detailed comments
def largestKPalindromic(n, k):
    # Calculate the length of "decision" positions.
    # For even n, we only need the first n//2 digits.
    # For odd n, we need the first n//2 digits plus the middle digit.
    is_odd = (n % 2 == 1)
    left_len = n // 2
    total_positions = left_len + (1 if is_odd else 0)
    
    # Precompute powers of 10 modulo k for every position in the full number.
    # Since n can be huge, compute only the required ones.
    modPow = [1] * (n + 1)
    for i in range(1, n + 1):
        modPow[i] = (modPow[i-1] * 10) % k
        
    # Precompute the multiplier for each decision position.
    # For even n: for position i (0-indexed in the left half),
    #   the digit appears at index i and its mirror at index n-i-1.
    # For odd n: for positions 0..left_len-1, same as even,
    #   and the middle digit (position left_len) contributes once at index left_len.
    multipliers = []
    for i in range(left_len):
        # Contribution from the left half and its mirror:
        contrib = (modPow[n - i - 1] + modPow[i]) % k
        multipliers.append(contrib)
    if is_odd:
        # Middle digit contribution: at index left_len.
        multipliers.append(modPow[left_len] % k)
    
    # Use memoization for DP: state (pos, current_mod)
    memo = {}
    
    # Backtracking function to assign digits for positions [pos, total_positions-1]
    def dp(pos, current_mod):
        if pos == total_positions:
            # Found a full assignment; check if the modulo sum is zero.
            return (current_mod % k) == 0
        # Check memoized result
        if (pos, current_mod) in memo:
            return memo[(pos, current_mod)]
        
        # Determine the valid digit range.
        # The first digit (pos==0) cannot be 0.
        start = 9
        end = 0
        for digit in range(start, end - 1, -1):
            if pos == 0 and digit == 0:
                continue  # leading digit cannot be 0
            new_mod = (current_mod + digit * multipliers[pos]) % k
            if dp(pos + 1, new_mod):
                memo[(pos, current_mod)] = True
                return True
        memo[(pos, current_mod)] = False
        return False

    # Check feasibility from starting state.
    if not dp(0, 0):
        return "-1"
    
    # Construct solution string using greedy decisions.
    result_digits = []
    current_mod = 0
    for pos in range(total_positions):
        chosen_digit = None
        for digit in range(9, -1, -1):
            if pos == 0 and digit == 0:
                continue  # skip leading zero
            new_mod = (current_mod + digit * multipliers[pos]) % k
            # If a valid completion exists:
            if dp(pos + 1, new_mod):
                chosen_digit = digit
                current_mod = new_mod
                result_digits.append(str(digit))
                break
        # Safety check - should not happen.
        if chosen_digit is None:
            return "-1"  
    # Build the full palindrome from the chosen half.
    if is_odd:
        left_half = result_digits[:left_len]
        middle_digit = result_digits[left_len]
        full_palindrome = "".join(left_half) + middle_digit + "".join(left_half[::-1])
    else:
        full_palindrome = "".join(result_digits) + "".join(result_digits[::-1])
    return full_palindrome

# Example test cases:
print(largestKPalindromic(3, 5))   # Expected output: "595"
print(largestKPalindromic(1, 4))   # Expected output: "8"
print(largestKPalindromic(5, 6))   # Expected output: "89898"