aboutsummaryrefslogtreecommitdiff
path: root/find_count_good_int.py
blob: 0b7f0bf7619b0268f8caac911bd4c8b316264827 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
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))