# Find the Count of Good Integers
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-the-count-of-good-integers)
Canonical: https://scaleengineer.com/dsa/problems/find-the-count-of-good-integers
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Hash Table
---
## Problem
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:

* 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 <= 10`
* `1 <= k <= 9`

# Approaches
## Combinatorial Approach by Iterating Multisets
This method is based on the idea that all integers which are permutations of each other are either all "good" or all "not good". Therefore, we can count the good integers by first finding all unique "good" digit multisets. A multiset is "good" if its digits can form a k-palindromic number. The approach iterates through every possible multiset of `n` digits, checks if it's good, and if so, calculates the number of `n`-digit integers that can be formed from it and adds to the total.
**Time:** O(C(n+9, 9) * h! * n) where `h = ceil(n/2)`. `C(n+9, 9)` is the number of multisets. For each, we may generate up to `h!` permutations of the first half, and each check takes `O(n)`. · **Space:** O(n) for the recursion stack depth and to store the counts array.
**Pros:** Correctly groups numbers by their digit multiset, avoiding redundant checks for permutations of the same number.; More systematic than a naive brute-force over all n-digit numbers.
**Cons:** The number of multisets can be large (`C(n+9, 9)`), and for each, we might need to generate many permutations of its first half.; The implementation is complex, especially the part that checks for k-divisibility by generating permutations.; Likely to be too slow for the given constraints, as it may time out.
### Explanation
The core of this approach is to work with digit frequency counts (multisets) instead of individual numbers.
First, we need a way to generate all possible multisets of size `n` using digits 0-9. This can be achieved with a recursive backtracking function. The function would explore how many times each digit (0 through 9) can be included, ensuring the total count of digits sums to `n`.
For each generated multiset, we perform two checks:
1.  **Palindrome Feasibility:** A multiset of digits can be arranged into a palindrome if and only if at most one digit appears an odd number of times. If this condition fails, the multiset cannot form any palindrome and is discarded.
2.  **K-Palindromic Feasibility:** If a palindrome can be formed, we need to determine if at least one of its palindromic arrangements is divisible by `k`. To do this, we construct the multiset for the first half of the palindrome. Then, we generate all unique permutations of this first-half multiset. Each permutation forms the first `ceil(n/2)` digits of a candidate palindrome. We construct the full palindrome and check for divisibility by `k`. If we find one such palindrome, the original multiset is confirmed to be "good", and we can stop checking other permutations for it.
If a multiset is found to be "good", we calculate the number of distinct `n`-digit integers that can be formed using its digits. This is a classic permutation with repetition problem. The total number of permutations is `n! / (c₀! * c₁! * ... * c₉!)`, where `cᵢ` is the count of digit `i`. From this, we must subtract the permutations that have a leading zero, which is calculated as `(n-1)! / ((c₀-1)! * c₁! * ... * c₉!)` if `c₀ > 0`.
The final result is the sum of these counts over all unique "good" multisets.
```java
// Conceptual structure
class Solution {
    long total = 0;
    int n, k;
    long[] fact;

    public int countGoodIntegers(int n, int k) {
        this.n = n;
        this.k = k;
        // Precompute factorials
        fact = new long[n + 1];
        fact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = fact[i - 1] * i;
        }

        generateMultisets(0, n, new int[10]);
        return (int) total;
    }

    void generateMultisets(int digit, int remaining, int[] counts) {
        if (digit == 10) {
            if (remaining == 0) {
                processMultiset(counts);
            }
            return;
        }

        for (int i = 0; i <= remaining; i++) {
            counts[digit] = i;
            generateMultisets(digit + 1, remaining - i, counts);
        }
        counts[digit] = 0; // backtrack
    }

    void processMultiset(int[] counts) {
        int oddCounts = 0;
        for (int count : counts) {
            if (count % 2 != 0) {
                oddCounts++;
            }
        }
        if (oddCounts > 1) return;

        if (isGoodMultiset(counts)) {
            long perms = fact[n];
            for (int count : counts) {
                perms /= fact[count];
            }
            if (counts[0] > 0) {
                long invalidPerms = fact[n - 1];
                invalidPerms /= fact[counts[0] - 1];
                for (int i = 1; i < 10; i++) {
                    invalidPerms /= fact[counts[i]];
                }
                perms -= invalidPerms;
            }
            total += perms;
        }
    }

    boolean isGoodMultiset(int[] counts) {
        // ... logic to check for k-palindromic feasibility ...
        // This involves generating permutations of the first half,
        // constructing the palindrome, and checking divisibility by k.
        // This part is complex to implement fully here.
        return false; // Placeholder
    }
}
```
### Algorithm
- 1. Define a recursive function `generateMultisets(digit, remaining_n, counts)` to generate all multisets of size `n`.
- 2. In the base case of the recursion (when all 10 digits have been considered and `remaining_n` is 0), process the generated multiset.
- 3. To process a multiset, first check if it can form a palindrome (at most one digit has an odd count).
- 4. If it can, check if any of the possible palindromes are divisible by `k`. This requires generating permutations of the first half's digits, forming the full palindrome, and checking `palindrome % k == 0`.
- 5. If a k-divisible palindrome exists for the multiset, calculate the number of valid `n`-digit permutations of the multiset and add it to a running total.
- 6. The number of permutations is `n! / (c₀! * ... * c₉!)`. If the multiset contains zeros, subtract the invalid permutations starting with zero: `(n-1)! / ((c₀-1)! * ... * c₉!)`.

## Generate Palindromes and Count Permutations
This is a highly efficient approach that directly generates the objects of interest: n-digit palindromes. It iterates through all possible first halves of an n-digit palindrome, constructs the full palindrome, and checks if it's divisible by `k`. The digit multisets of all such valid palindromes are stored in a set to ensure uniqueness. Finally, for each unique multiset, it calculates the number of corresponding good integers (n-digit permutations) and sums them up.
**Time:** O(10^h * n), where `h = (n+1)/2`. The loop runs `O(10^h)` times. Inside the loop, constructing the palindrome, getting the multiset key, and set insertion take `O(n)`. The final counting step also takes at most `O(10^h * n)`. · **Space:** O(10^h * n) to store the unique multiset keys in the worst case, where `h = (n+1)/2`.
**Pros:** Very efficient as it directly generates only the necessary palindromes.; The number of palindromes to check is relatively small (`9 * 10^((n+1)/2 - 1)`), making it fast even for `n=10`.; Using a set for multisets elegantly handles duplicates.
**Cons:** Requires careful implementation of palindrome construction from the first half.; Space complexity depends on the number of unique valid multisets, which could be large in theory, but is manageable for the given constraints.
### Explanation
An `n`-digit palindrome is uniquely determined by its first `h = ceil(n/2)` digits. For example, if `n=5`, the first 3 digits (e.g., `123`) define the palindrome (`12321`). If `n=4`, the first 2 digits (e.g., `12`) define the palindrome (`1221`).
The first half must be an `h`-digit number, meaning its first digit cannot be zero. So, we can iterate through all numbers from `10^(h-1)` to `10^h - 1` to represent all possible first halves.
The algorithm proceeds as follows:
1.  Calculate `h = (n+1)/2`.
2.  Initialize a `Set` to store the canonical representations of digit multisets of valid k-palindromes. A canonical representation can be a sorted string of the digits.
3.  Loop through each possible `first_half` number from `10^(h-1)` to `10^h - 1`.
4.  Inside the loop, construct the full `n`-digit palindrome `p`.
5.  Check if `p` is divisible by `k`.
6.  If `p % k == 0`, determine its digit multiset, create a canonical representation (e.g., sort the digits and form a string), and add it to the set. Using a set automatically handles cases where different palindromes (like 1221 and 2112) might have the same multiset.
7.  After the loop finishes, iterate through the unique multisets in the set.
8.  For each unique multiset, calculate the number of distinct `n`-digit integers that can be formed from it, being careful to exclude permutations with leading zeros.
9.  Sum these counts to get the final answer.
```java
import java.util.*;

class Solution {
    public int countGoodIntegers(int n, int k) {
        int h = (n + 1) / 2;
        long start = (long) Math.pow(10, h - 1);
        long end = (long) Math.pow(10, h) - 1;

        Set<String> validMultisets = new HashSet<>();

        for (long i = start; i <= end; i++) {
            long p = constructPalindrome(i, n);
            if (p % k == 0) {
                validMultisets.add(getMultisetKey(p));
            }
        }

        long totalGoodIntegers = 0;
        long[] fact = new long[n + 1];
        fact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = fact[i - 1] * i;
        }

        for (String multisetKey : validMultisets) {
            int[] counts = new int[10];
            for (char c : multisetKey.toCharArray()) {
                counts[c - '0']++;
            }

            long perms = fact[n];
            for (int count : counts) {
                perms /= fact[count];
            }

            if (counts[0] > 0) {
                long invalidPerms = fact[n - 1];
                invalidPerms /= fact[counts[0] - 1];
                for (int i = 1; i < 10; i++) {
                    invalidPerms /= fact[counts[i]];
                }
                perms -= invalidPerms;
            }
            totalGoodIntegers += perms;
        }

        return (int) totalGoodIntegers;
    }

    private long constructPalindrome(long firstHalf, int n) {
        String s1 = String.valueOf(firstHalf);
        String s2 = new StringBuilder(s1.substring(0, n / 2)).reverse().toString();
        return Long.parseLong(s1 + s2);
    }

    private String getMultisetKey(long p) {
        char[] chars = String.valueOf(p).toCharArray();
        Arrays.sort(chars);
        return new String(chars);
    }
}
```
### Algorithm
- 1. Determine the length of the first half of the palindrome, `h = (n+1)/2`.
- 2. Iterate through all possible `h`-digit numbers for the first half. The range is `[10^(h-1), 10^h - 1]`.
- 3. For each `first_half` number, construct the full `n`-digit palindrome `p`.
- 4. If `p` is divisible by `k`, compute its digit multiset and store a canonical representation (e.g., a sorted string of its digits) in a `HashSet` to keep track of unique valid multisets.
- 5. After checking all possible first halves, iterate through the unique multisets found.
- 6. For each multiset, calculate the number of `n`-digit permutations, subtracting those that start with a zero.
- 7. Sum up the counts for all unique multisets to get the final result.

# Solutions
### Java

```java
class 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;
  }
}

```

### JavaScript

```javascript
/** * @param {number} n * @param {number} k * @return {number} */ var countGoodIntegers =
  function (n, k) {
    const fac = factorial(n);
    let ans = 0;
    const vis = new Set();
    const base = Math.pow(10, Math.floor((n - 1) / 2));
    for (let i = base; i < base * 10; i++) {
      let s = String(i);
      const rev = reverseString(s);
      if (n % 2 === 1) {
        s += rev.substring(1);
      } else {
        s += rev;
      }
      if (parseInt(s, 10) % 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[parseInt(c, 10)]++;
      }
      let res = (n - cnt[0]) * fac[n - 1];
      for (const x of cnt) {
        res /= fac[x];
      }
      ans += res;
    }
    return ans;
  };
function factorial(n) {
  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) {
  return s.split("").reverse().join("");
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 ans

```