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.
This approach uses backtracking to generate all possible k-palindromic integers with n digits. It checks if a number can be rearranged into such a structure.
The code generates numbers with a given number of digits and checks if they are k-palindromic. It converges by backtracking through all possible numbers.
Time complexity is O(9^n), and space complexity is O(n) due to the recursion stack.
This approach sets up a Dynamic Programming (DP) table to store solutions of sub-problems involving palindromicity checks and divisibility, reducing repetition.
Implementing the Dynamic Programming approach in C involves understanding prior states and calculations, focusing on efficient combination management and k-palindromicity checks.
Time complexity and space complexity would depend on sub-problem calculations saving substantial reduction from naive method.
We can consider enumerating all palindromic numbers of length n and checking whether they are k-palindromic numbers. Due to the properties of palindromic numbers, we only need to enumerate the first half of the digits and then reverse and append them to form the full number.
The length of the first half of the digits is \lfloor \frac{n - 1}{2} \rfloor, so the range of the first half is [10^{\lfloor \frac{n - 1}{2} \rfloor}, 10^{\lfloor \frac{n - 1}{2} \rfloor + 1}). We can reverse the first half and append it to form a palindromic number of length n. Note that if n is odd, the middle digit needs special handling.
Next, we check whether the palindromic number is k-palindromic. If it is, we count all unique permutations of the number. To avoid duplicates, we can use a set vis to store the smallest permutation of each palindromic number that has already been processed. If the smallest permutation of the current palindromic number is already in the set, we skip it. Otherwise, we calculate the number of unique permutations of the palindromic number and add it to the result.
We can use an array cnt to count the occurrences of each digit and use combinatorics to calculate the number of permutations. Specifically, if digit 0 appears x_0 times, digit 1 appears x_1 times, ..., and digit 9 appears x_9 times, the number of permutations of the palindromic number is:
$
\frac{(n - x_0) cdot (n - 1)!}{x_0! cdot x_1! cdots x_9!}
Here, (n - x_0) represents the number of choices for the highest digit (excluding 0), (n - 1)! represents the permutations of the remaining digits, and we divide by the factorial of the occurrences of each digit to avoid duplicates.
Finally, we sum up all the permutation counts to get the final result.
Time complexity is O(10^m times n times log n), and space complexity is O(10^m times n), where m = \lfloor \frac{n - 1}{2} \rfloor$.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time complexity is O(9^n), and space complexity is O(n) due to the recursion stack. |
| Dynamic Programming Approach | Time complexity and space complexity would depend on sub-problem calculations saving substantial reduction from naive method. |
| Enumeration + Combinatorics | — |
| 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. |
Find the Count of Good Integers | Detailed Approach | Step By Step | Leetcode 3272 |codestorywithMIK • codestorywithMIK • 9,960 views views
Watch 9 more video solutions →Practice Find the Count of Good Integers with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor