# 3272. Find the Count of Good Integers
from math import factorial
from collections import Counter
"""
you are given two positive integers 'n' and 'k'. an integer 'x' is called
k-palindromic if 'x' is a palindrome and 'x' is divisble 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, wherase 1010 cannot be rearranged to form a
k-palindromic integer. return the count of good integers containing 'n'
digits.
"""
class Solution(object):
def __init__(self):
self.ans = 0
self.vis = set()
def to_num(self, digits):
return int("".join(map(str, digits)))
def permutation_cnt(self, freq, total):
res = factorial(total)
for i in freq.values():
res //= factorial(i)
return res
def permutation_leading_zero(self, freq, total):
if freq.get(0, 0) == 0:
return 0
freq[0] -= 1
res = factorial(total - 1)
for i in freq.values():
res //= factorial(i)
return res
def gen_palindrome(self, palin, left, right, divisor, total):
if left > right:
val = self.to_num(palin)
if val % divisor == 0:
freq = Counter(palin)
key = tuple(sorted(freq.items()))
if key not in self.vis:
self.ans += self.permutation_cnt(
freq, total
) - self.permutation_leading_zero(freq.copy(), total)
self.vis.add(key)
return
for i in range(1 if left == 0 else 0, 10):
palin[left] = palin[right] = i
self.gen_palindrome(palin, left + 1, right - 1, divisor, total)
def countGoodIntegers(self, n, k):
"""
:type n: int
:type k: int
:rtype: int
"""
self.ans = 0
self.vis.clear()
self.gen_palindrome([0] * n, 0, n - 1, k, n)
return self.ans
if __name__ == "__main__":
obj = Solution()
print(obj.countGoodIntegers(n=3, k=5))
print(obj.countGoodIntegers(n=1, k=4))
print(obj.countGoodIntegers(n=5, k=6))
