aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--find_count_good_int.c115
-rw-r--r--find_count_good_int.py71
2 files changed, 186 insertions, 0 deletions
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))