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 thelargest integer having n digits (as a string) that is k-palindromic.

Note that the integer must not have leading zeros.

Examples

Example 1

1
2
3
4
5
6
7
8


Input: n = 3, k = 5

Output: "595"

Explanation:

595 is the largest k-palindromic integer with 3 digits.

Example 2

1
2
3
4
5
6
7
8


Input: n = 1, k = 4

Output: "8"

Explanation:

4 and 8 are the only k-palindromic integers with 1 digit.

Example 3

1
2
3
4


Input: n = 5, k = 6

Output: "89898"

Constraints

  • 1 <= n <= 10^5
  • 1 <= k <= 9

Solution

Method 1 – Greedy Palindrome Construction + Modular Check

Intuition

The largest n-digit palindrome is formed by filling the highest possible digits from the outside in. To find the largest k-palindromic number, generate palindromes from largest to smallest and check divisibility by k. For efficiency, construct only valid palindromes and check divisibility.

Approach

  1. For n digits, the largest palindrome is formed by mirroring the first half (for odd n, the middle digit is unique).
  2. Iterate from the largest possible first half down to the smallest (respecting no leading zeros).
  3. For each candidate, construct the full palindrome and check if it is divisible by k.
  4. Return the first such palindrome found as a string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    string largestPalindromic(int n, int k) {
        int half = (n + 1) / 2;
        long long start = pow(10, half - 1), end = pow(10, half) - 1;
        for (long long i = end; i >= start; --i) {
            string s = to_string(i);
            string rev = s.substr(0, n / 2);
            reverse(rev.begin(), rev.end());
            string pal = s + rev;
            long long num = stoll(pal);
            if (num % k == 0) return pal;
        }
        return "";
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func largestPalindromic(n int, k int) string {
    half := (n + 1) / 2
    start := int(math.Pow10(half - 1))
    end := int(math.Pow10(half)) - 1
    for i := end; i >= start; i-- {
        s := strconv.Itoa(i)
        rev := reverse(s[:n/2])
        pal := s + rev
        num, _ := strconv.Atoi(pal)
        if num%k == 0 {
            return pal
        }
    }
    return ""
}
func reverse(s string) string {
    b := []byte(s)
    for i, j := 0, len(b)-1; i < j; i, j = i+1, j-1 {
        b[i], b[j] = b[j], b[i]
    }
    return string(b)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public String largestPalindromic(int n, int k) {
        int half = (n + 1) / 2;
        int start = (int)Math.pow(10, half - 1), end = (int)Math.pow(10, half) - 1;
        for (int i = end; i >= start; i--) {
            String s = Integer.toString(i);
            String rev = new StringBuilder(s.substring(0, n / 2)).reverse().toString();
            String pal = s + rev;
            if (new java.math.BigInteger(pal).mod(java.math.BigInteger.valueOf(k)).equals(java.math.BigInteger.ZERO))
                return pal;
        }
        return "";
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun largestPalindromic(n: Int, k: Int): String {
        val half = (n + 1) / 2
        val start = Math.pow(10.0, (half - 1).toDouble()).toInt()
        val end = Math.pow(10.0, half.toDouble()).toInt() - 1
        for (i in end downTo start) {
            val s = i.toString()
            val rev = s.substring(0, n / 2).reversed()
            val pal = s + rev
            if (pal.toBigInteger().mod(k.toBigInteger()) == 0.toBigInteger())
                return pal
        }
        return ""
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def largest_palindromic(n: int, k: int) -> str:
    half = (n + 1) // 2
    start = 10 ** (half - 1)
    end = 10 ** half - 1
    for i in range(end, start - 1, -1):
        s = str(i)
        rev = s[:n // 2][::-1]
        pal = s + rev
        if int(pal) % k == 0:
            return pal
    return ""
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn largest_palindromic(n: i32, k: i32) -> String {
        let half = (n + 1) / 2;
        let start = 10_i64.pow((half - 1) as u32);
        let end = 10_i64.pow(half as u32) - 1;
        for i in (start..=end).rev() {
            let s = i.to_string();
            let rev: String = s.chars().take((n / 2) as usize).rev().collect();
            let pal = format!("{}{}", s, rev);
            let num = pal.parse::<i64>().unwrap();
            if num % (k as i64) == 0 {
                return pal;
            }
        }
        String::new()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    largestPalindromic(n: number, k: number): string {
        const half = Math.floor((n + 1) / 2);
        const start = Math.pow(10, half - 1);
        const end = Math.pow(10, half) - 1;
        for (let i = end; i >= start; i--) {
            const s = i.toString();
            const rev = s.slice(0, Math.floor(n / 2)).split('').reverse().join('');
            const pal = s + rev;
            if (BigInt(pal) % BigInt(k) === 0n) return pal;
        }
        return "";
    }
}

Complexity

  • ⏰ Time complexity: O(10^{n/2} * n), as we may check up to 10^{n/2} palindromes, each of length n.
  • 🧺 Space complexity: O(n), for string construction and storage.