Watch 10 video solutions for Find the Count of Good Integers, a hard level problem involving Hash Table, Math, Combinatorics. This walkthrough by codestorywithMIK has 9,960 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 9Problem Overview: Given integers n and k, count how many n-digit integers are considered good. A number is good if its digits can be rearranged to form a palindrome that is divisible by k. The challenge is avoiding duplicate digit permutations while ensuring the palindrome divisibility condition.
Approach 1: Backtracking Enumeration (≈ O(10^(n/2)) time, O(10^(n/2)) space)
Instead of enumerating every n-digit number, generate only palindromes. Build the first half using backtracking, mirror it to form the full palindrome, and compute value % k. When the palindrome is divisible by k, record its digit frequency signature (for example, a 10-length digit count array serialized as a string) in a hash table to avoid duplicates. For each unique digit multiset, compute how many valid n-digit permutations exist using combinatorics with factorials while subtracting cases that start with zero. This approach drastically reduces search space because only half of the digits are explored.
Approach 2: Dynamic Programming with Combinatorics (≈ O(n * k * states) time, O(k * states) space)
A more structured solution tracks how digits are distributed while maintaining the remainder modulo k. Use DP states that represent partial palindrome construction and remainder after placing symmetric digits. Each transition adds a digit pair (or a middle digit when n is odd) and updates the modulo contribution. After generating valid digit frequency states that produce mod k = 0, count the number of valid permutations using factorial-based formulas while ensuring the first digit is non-zero. This technique combines math reasoning with state compression to avoid explicit enumeration.
Recommended for interviews: The backtracking enumeration approach is usually easier to explain. You show the key insight: generate palindromes directly, deduplicate using a hash signature, then count permutations with combinatorics. Interviewers expect this reasoning because it reduces brute-force search from all n-digit numbers to only palindrome candidates. The dynamic programming variant demonstrates stronger optimization skills and deeper understanding of remainder transitions.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking Palindrome Enumeration | O(10^(n/2)) | O(10^(n/2)) | Best when n is moderate. Directly generates palindrome candidates and deduplicates using digit frequency hashing. |
| Dynamic Programming with Remainder States | O(n * k * states) | O(k * states) | Useful when optimizing enumeration or reasoning about remainder transitions while building palindromes. |