Find the Count of Good Integers

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.

• 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.

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.

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);
    }
}