Find the Count of Good Integers - Solution & Explanation
Problem Statement
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
Approach Overview
Problem 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 1: Backtracking Approach
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.
Complexity
Time complexity is O(9^n), and space complexity is O(n) due to the recursion stack.
Approach 2: Dynamic Programming Approach
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.
Complexity
Time complexity and space complexity would depend on sub-problem calculations saving substantial reduction from naive method.
Approach 3: Enumeration + Combinatorics
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$.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
Complexity Comparison
| 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 | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Find the Count of Good Integers | Detailed Approach | Step By Step | Leetcode 3272 |codestorywithMIK • codestorywithMIK • 10,212 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find the Count of Good Integers easy or hard?
Find the Count of Good Integers Python/Java solution
How to solve Find the Count of Good Integers in O(10^(n/2))?
What is the best approach for Find the Count of Good Integers?
Is Find the Count of Good Integers asked at Google/Amazon/Meta?
What data structure is used in Find the Count of Good Integers?
What is the time complexity of Find the Count of Good Integers?
Ready to solve this problem?
Practice Find the Count of Good Integers with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor