diff options
Diffstat (limited to 'find_count_good_int.py')
-rw-r--r-- | find_count_good_int.py | 71 |
1 files changed, 71 insertions, 0 deletions
diff --git a/find_count_good_int.py b/find_count_good_int.py new file mode 100644 index 0000000..0b7f0bf --- /dev/null +++ b/find_count_good_int.py @@ -0,0 +1,71 @@ +# 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)) |