3272. Find the Count of Good Integers

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.

An integer is called good if its digits can be rearranged to form a k-palindromic integer. For example, for k = 2, 2020 can be rearranged to form the k-palindromic integer 2002, whereas 1010 cannot be rearranged to form a k-palindromic integer.

Return the count of good integers containing n digits.

Note that any integer must not have leading zeros, neither before nor after rearrangement. For example, 1010 cannot be rearranged to form 101.

 

Example 1:

Input: n = 3, k = 5

Output: 27

Explanation:

Some of the good integers are:

• 551 because it can be rearranged to form 515.
• 525 because it is already k-palindromic.

Example 2:

Input: n = 1, k = 4

Output: 2

Explanation:

The two good integers are 4 and 8.

Example 3:

Input: n = 5, k = 6

Output: 2468

 

Constraints:

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

Solution

---

Python3

class Solution:
    def countGoodIntegers(self, n: int, k: int) -> int:
        n2 = (n + 1) // 2
        res = 0
        seen = set()
        for v in range(10 ** (n2 - 1), 10 ** n2):
            vv = str(v) + str(v)[::-1][n % 2:]
            key = ''.join(sorted(vv))
            if int(vv) % k == 0 and key not in seen:
                seen.add(key)
                count = Counter(vv)
                x = (n - count['0']) * factorial(n - 1)
                for i,c in count.items():
                    x //= factorial(c)
                res += x
        return res