You are given two positive integers n and k.
An integer x is called k-palindromic if:
x is a palindrome.x is divisible 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, 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:
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 <= 9In #3272 Find the Count of Good Integers, the key idea is to recognize that directly enumerating every possible n-digit integer is infeasible. Instead, observe that a number is considered good if its digits can be rearranged to form a valid palindrome that is divisible by k. This allows us to reverse the thinking: rather than checking all integers, we enumerate candidate palindromes and analyze their digit compositions.
Generate all palindromes of length n and check whether they are divisible by k. For each valid palindrome, record its digit frequency signature (e.g., using a hashable representation). This avoids double-counting permutations that produce the same multiset of digits. Once unique digit-frequency patterns are identified, apply combinatorics to compute how many distinct n-digit numbers can be formed from that multiset, while ensuring no leading zero occurs.
This approach combines enumeration, hash sets for deduplication, and factorial-based permutation counting. The search space is reduced to roughly half-length palindrome construction, making it manageable for typical constraints.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Palindrome Enumeration + Hashing + Combinatorics | O(10^(n/2) * n) | O(U) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
How to generate all K-palindromic strings of length <code>n</code>? Do we need to go through all <code>n</code> digits?
Use permutations to calculate the number of possible rearrangements.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Hashing helps store unique digit-frequency signatures of valid palindromes. This prevents counting the same multiset of digits multiple times when different palindromes share identical digit compositions.
Problems combining combinatorics, enumeration, and hashing frequently appear in FAANG-style interviews. While this exact problem may not always appear, the techniques used—palindrome generation, counting permutations, and deduplication—are commonly tested.
A hash set or hash map is ideal for storing digit frequency signatures. It enables fast deduplication while enumerating palindromes and ensures each digit pattern is processed only once.
The optimal strategy is to enumerate palindromes of length n and check which ones are divisible by k. For each valid palindrome, store its digit frequency pattern and use combinatorics to count how many n-digit integers can be formed from that pattern without leading zeros.