Skip to main content
Back to problems
#3260
Hard Algorithms

Find the largest palindrome divisible by k

Math String Dynamic Programming Greedy Number Theory
16.9% acceptance
Feb 25, 2026
108
70
You are given two positive integers n and k. Return the largest integer having n digits that is both a palindrome and divisible by k.

Solution

Rust
Time O(n³)
Space O(n)
LeetCode
solution.rs 
impl Solution {
  pub fn largest_palindrome(n: i32, k: i32) -> String {
    let n = n as usize;
    let k = k as usize;

    // Trivial case: every number is divisible by 1
    if k == 1 {
      return "9".repeat(n);
    }

    let h = (n + 1) / 2; // free digits: left half + optional middle

    // Precompute 10^i mod k for all i in O(n) instead of O(n²)
    let mut pow10 = vec![0usize; n];
    pow10[0] = 1 % k;
    for i in 1..n {
      pow10[i] = (pow10[i - 1] * 10) % k;
    }

    // Weight of free position i:
    // For i < n-1-i (not middle): contributes to positions i and n-1-i → w = (10^(n-1-i) + 10^i) % k
    // For i == n-1-i (middle, n odd): w = 10^i % k
    let mut ws = vec![0usize; h];
    for i in 0..h {
      let mirror = n - 1 - i;
      if i == mirror {
        ws[i] = pow10[i];
      } else {
        ws[i] = (pow10[i] + pow10[mirror]) % k;
      }
    }

    // reach[i][r] = true iff d[i..h-1] (each 0..9) can sum to r mod k
    // k <= 9, so indices 0..k fit in [false; 9]
    let mut reach = vec![[false; 9]; h + 1];
    reach[h][0] = true;
    for i in (0..h).rev() {
      for r in 0..k {
        for d in 0..10usize {
          let dw = (d * ws[i]) % k;
          let sub = (k + r - dw) % k;
          if reach[i + 1][sub] {
            reach[i][r] = true;
            break;
          }
        }
      }
    }

    // Greedy: at each position, try largest digit first
    let mut digits = vec![0u8; h];
    let mut acc = 0usize; // accumulated sum mod k (d[0..i] contribution)
    for i in 0..h {
      let needed = (k - acc) % k; // need d[i..h-1] to contribute this mod k
      let start_d = if i == 0 { 1usize } else { 0 };
      for d in (start_d..=9usize).rev() {
        let dw = (d * ws[i]) % k;
        let sub_needed = (k + needed - dw) % k;
        if reach[i + 1][sub_needed] {
          digits[i] = d as u8;
          acc = (acc + dw) % k;
          break;
        }
      }
    }

    // Build palindrome string
    // First half (including middle if n odd): digits[0..h]
    // Mirror: digits[0..h-1] reversed (excluding middle) for n odd, digits[0..h] reversed for n even
    let mirror_len = if n % 2 == 1 { h - 1 } else { h };
    let mut result = Vec::with_capacity(n);
    result.extend(digits[0..h].iter().map(|&d| b'0' + d));
    result.extend(digits[0..mirror_len].iter().rev().map(|&d| b'0' + d));
    String::from_utf8(result).unwrap()
  }
}