Skip to content

3260. Find the Largest Palindrome Divisible by K

Description

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

Solutions

Solution 1

Thinking

Build the largest \(n\)-digit palindrome divisible by \(k\), with \(n\le 10^5\) and \(k\le 9\). Listing palindromes downward is impossible; the first half determines the rest, and we only need the value modulo \(k\).

Case on \(k\) (last digits for \(2,4,5,8\), digit sum for \(3,9\), both for \(6,7\)), greedily fill nines and fix the lowest positions so the whole number is \(0\bmod k\). There is no implementation in the tree yet; the reasoning is “fix the first half, repair the tail for \(k\)”.

1


1


1


1

Comments