From e5068470c3758c57f1b59c7dde1d32670a5a12c9 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Fri, 11 Apr 2025 22:54:23 -0600 Subject: 3272. find the count of good integers --- find_count_good_int.c | 115 +++++++++++++++++++++++++++++++++++++++++++++++++ find_count_good_int.py | 71 ++++++++++++++++++++++++++++++ 2 files changed, 186 insertions(+) create mode 100644 find_count_good_int.c create mode 100644 find_count_good_int.py diff --git a/find_count_good_int.c b/find_count_good_int.c new file mode 100644 index 0000000..d69105e --- /dev/null +++ b/find_count_good_int.c @@ -0,0 +1,115 @@ +// 3272. Find the Count of Good Integers +#include "leetcode.h" + +/* + * 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. + */ + +#define HASH_SIZE (1 << 17) + +static unsigned long long vis[HASH_SIZE]; +static long long fact[11], ans; + +static inline uint hash(unsigned long long key) { + return (uint)(key % HASH_SIZE); +} + +bool insert(unsigned long long key) { + uint idx = hash(key); + while (true) { + if (!vis[idx]) { + vis[idx] = key; + return true; + } else if (vis[idx] == key) + return false; + idx = (idx + 1) & (HASH_SIZE - 1); + } +} + +void hash_init(void) { + fact[0] = 1; + for (int i = 1; i <= 10; i++) + fact[i] = fact[i - 1] * i; +} + +long long permutation_cnt(int *freq, int n) { + long long total = fact[n]; + for (int i = 0; i < 10; i++) + total /= fact[freq[i]]; + return total; +} + +long long permutation_lead_zero(int *freq, int n) { + if (!freq[0]) + return 0; + int copy[10]; + memcpy(copy, freq, sizeof(int) * 10); + copy[0]--; + long long total = fact[n - 1]; + for (int i = 0; i < 10; i++) + total /= fact[copy[i]]; + return total; +} + +long long multiset(int *freq, int n) { + long long total = permutation_cnt(freq, n); + long long lz = permutation_lead_zero(freq, n); + return total - lz; +} + +unsigned long long encode_freq(int *freq) { + unsigned long long enc = 0; + for (int i = 0; i < 10; i++) + enc |= ((unsigned long long)freq[i] & 0xCAFE) << (4 * i); + return enc; +} + +long long to_num(int *num, int n) { + long long res = 0; + for (int i = 0; i < n; i++) + res *= 10 + num[i]; + return res; +} + +void gen_palindrome(int *num, int left, int right, int n, int k) { + if (left > right) { + long long candidtate = to_num(num, n); + if (!(candidtate % k)) { + int freq[10] = {0}; + for (int i = 0; i < n; i++) + freq[num[i]]++; + unsigned long long code = encode_freq(freq); + if (insert(code)) + ans += multiset(freq, n); + } + return; + } + int start = !left ? 1 : 0; + for (int i = start; i <= 9; i++) { + num[left] = i; + num[right] = i; + gen_palindrome(num, left + 1, right - 1, n, k); + } +} + +long long countGoodIntegers(int n, int k) { + ans = 0; + memset(vis, 0, sizeof(vis)); + hash_init(); + int *num = (int *)malloc(n * sizeof(int)); + gen_palindrome(num, 0, n - 1, n, k); + free(num); + return ans; +} + +int main() { + printf("%lld\n", countGoodIntegers(3, 5)); // expect: 27 + printf("%lld\n", countGoodIntegers(1, 4)); // expect: 2 + printf("%lld\n", countGoodIntegers(5, 6)); // expect: 2468 +} 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)) -- cgit v1.2.3