3260. Find the Largest Palindrome Divisible by K

Problem Link

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

Solution

---

Python3

class Solution:
    def largestPalindrome(self, n: int, k: int) -> str:
        if k == 1 or k == 3 or k == 9:
            return '9' * n
 
        if k == 2:
            if n <= 2:
                return '8' * n
            else:
                return '8' + '9' * (n - 2) + '8'
 
        if k == 4:
            if n <= 4:
                return '8' * n
            else:
                return '88' + '9' * (n - 4) + '88'
 
        if k == 5:
            if n <= 2:
                return '5' * n
            else:
                return '5' + '9' * (n - 2) + '5'
        
        if k == 8:
            if n <= 6:
                return '8' * n
            else:
                return '888' + '9' * (n - 6) + '888'
        
        if k == 6:
            # n = 5, 89898
            # n = 6, 897798
            # n = 7, 8998998
 
            if n <= 2:
                return '6' * n
            elif n % 2 == 1:
                half = n // 2 - 1
                return '8' + '9' * half + '8' + '9' * half + '8'
            else:
                half = n // 2 - 2
                return '8' + '9' * half + '77' + '9' * half + '8'
        
        if k == 7:
            # n = 2, 77
            # n = 3, 959
            # n = 4, 9779
            # n = 5, 99799
            # n = 6, 999999
            # n = 7, 9994999
 
            dic = {0: '', 1: '7', 2: '77', 3: '959', 4: '9779', 5: '99799', 6: '999999', 7: '9994999',
                       8: '99944999', 9: '999969999', 10: '9999449999', 11: '99999499999'}
            l, r = divmod(n, 12)
            return '999999' * l + dic[r] + '999999' * l