| comments | difficulty | edit_url | rating | source | tags | ||||
|---|---|---|---|---|---|---|---|---|---|
true |
Hard |
2382 |
Biweekly Contest 138 Q3 |
|
You are given two positive integers n and k.
An integer x is called k-palindromic if:
xis a palindrome.xis divisible byk.
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, whereas 1010 cannot be rearranged to form a k-palindromic integer.
Return the count of good integers containing n digits.
Note that any integer must not have leading zeros, neither before nor after rearrangement. For example, 1010 cannot be rearranged to form 101.
Example 1:
Input: n = 3, k = 5
Output: 27
Explanation:
Some of the good integers are:
- 551 because it can be rearranged to form 515.
- 525 because it is already k-palindromic.
Example 2:
Input: n = 1, k = 4
Output: 2
Explanation:
The two good integers are 4 and 8.
Example 3:
Input: n = 5, k = 6
Output: 2468
Constraints:
1 <= n <= 101 <= k <= 9
class Solution:
def countGoodIntegers(self, n: int, k: int) -> int:
fac = [factorial(i) for i in range(n + 1)]
ans = 0
vis = set()
base = 10 ** ((n - 1) // 2)
for i in range(base, base * 10):
s = str(i)
s += s[::-1][n % 2 :]
if int(s) % k:
continue
t = "".join(sorted(s))
if t in vis:
continue
vis.add(t)
cnt = Counter(t)
res = (n - cnt["0"]) * fac[n - 1]
for x in cnt.values():
res //= fac[x]
ans += res
return ansclass Solution {
public long countGoodIntegers(int n, int k) {
long[] fac = new long[n + 1];
fac[0] = 1;
for (int i = 1; i <= n; i++) {
fac[i] = fac[i - 1] * i;
}
long ans = 0;
Set<String> vis = new HashSet<>();
int base = (int) Math.pow(10, (n - 1) / 2);
for (int i = base; i < base * 10; i++) {
String s = String.valueOf(i);
StringBuilder sb = new StringBuilder(s).reverse();
s += sb.substring(n % 2);
if (Long.parseLong(s) % k != 0) {
continue;
}
char[] arr = s.toCharArray();
Arrays.sort(arr);
String t = new String(arr);
if (vis.contains(t)) {
continue;
}
vis.add(t);
int[] cnt = new int[10];
for (char c : arr) {
cnt[c - '0']++;
}
long res = (n - cnt[0]) * fac[n - 1];
for (int x : cnt) {
res /= fac[x];
}
ans += res;
}
return ans;
}
}class Solution {
public:
long long countGoodIntegers(int n, int k) {
vector<long long> fac(n + 1, 1);
for (int i = 1; i <= n; ++i) {
fac[i] = fac[i - 1] * i;
}
long long ans = 0;
unordered_set<string> vis;
int base = pow(10, (n - 1) / 2);
for (int i = base; i < base * 10; ++i) {
string s = to_string(i);
string rev = s;
reverse(rev.begin(), rev.end());
s += rev.substr(n % 2);
if (stoll(s) % k) {
continue;
}
string t = s;
sort(t.begin(), t.end());
if (vis.count(t)) {
continue;
}
vis.insert(t);
vector<int> cnt(10);
for (char c : t) {
cnt[c - '0']++;
}
long long res = (n - cnt[0]) * fac[n - 1];
for (int x : cnt) {
res /= fac[x];
}
ans += res;
}
return ans;
}
};func factorial(n int) []int64 {
fac := make([]int64, n+1)
fac[0] = 1
for i := 1; i <= n; i++ {
fac[i] = fac[i-1] * int64(i)
}
return fac
}
func countGoodIntegers(n int, k int) (ans int64) {
fac := factorial(n)
vis := make(map[string]bool)
base := int(math.Pow(10, float64((n-1)/2)))
for i := base; i < base*10; i++ {
s := strconv.Itoa(i)
rev := reverseString(s)
s += rev[n%2:]
num, _ := strconv.ParseInt(s, 10, 64)
if num%int64(k) != 0 {
continue
}
bs := []byte(s)
slices.Sort(bs)
t := string(bs)
if vis[t] {
continue
}
vis[t] = true
cnt := make([]int, 10)
for _, c := range t {
cnt[c-'0']++
}
res := (int64(n) - int64(cnt[0])) * fac[n-1]
for _, x := range cnt {
res /= fac[x]
}
ans += res
}
return
}
func reverseString(s string) string {
t := []byte(s)
for i, j := 0, len(t)-1; i < j; i, j = i+1, j-1 {
t[i], t[j] = t[j], t[i]
}
return string(t)
}function factorial(n: number): number[] {
const fac = Array(n + 1).fill(1);
for (let i = 1; i <= n; i++) {
fac[i] = fac[i - 1] * i;
}
return fac;
}
function reverseString(s: string): string {
return s.split('').reverse().join('');
}
function countGoodIntegers(n: number, k: number): number {
const fac = factorial(n);
let ans = 0;
const vis = new Set<string>();
const base = Math.pow(10, Math.floor((n - 1) / 2));
for (let i = base; i < base * 10; i++) {
let s = i.toString();
const rev = reverseString(s);
if (n % 2 === 1) {
s += rev.substring(1);
} else {
s += rev;
}
const num = parseInt(s, 10);
if (num % k !== 0) {
continue;
}
const bs = Array.from(s).sort();
const t = bs.join('');
if (vis.has(t)) {
continue;
}
vis.add(t);
const cnt = Array(10).fill(0);
for (const c of t) {
cnt[+c]++;
}
let res = (n - cnt[0]) * fac[n - 1];
for (const x of cnt) {
res /= fac[x];
}
ans += res;
}
return ans;
}