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 ca

countGoodIntegers.js

/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var countGoodIntegers = function(n, k) {
     // Precalculate factorial values for combinatorics
    const memoF = Array(n); // Memoization array for factorial values
    memoF[0] = 1; // Base case: 0! = 1
    for (let i = 1; i < n; i++) {
        memoF[i] = memoF[i - 1] * (i + 1); // Fill factorial values iteratively
    }

    // Function for calculating combinations C(len, freq)
    const C = (len, freq) => {
        if (len === freq) return 1; // If all elements are chosen
        if (freq === 1) return len; // If choosing one element from len
        const len1 = len - 1;
        const freq1 = freq - 1;
        // Return C(len, freq) = len! / [(len-freq)! * freq!]
        return (memoF[len1] / memoF[len1 - freq]) / memoF[freq1];
    };

    let total = 0; // Count of "good" integers
    const num = Array(n).fill(0); // Array representing the number being built
    const maxDepth = Math.ceil(n / 2) - 1; // Recursive depth for palindromes
    const was = new Set(); // Set to track unique sorted permutations

    // Recursive helper function to generate palindromes and check divisibility
    const helper = (curDepth) => {
        if (curDepth === maxDepth) {
            // If the middle of the number is reached, try all digits
            for (let i = 0; i <= 9; i++) {
                num[curDepth] = i; // Place the digit at the current depth
                num[n - curDepth - 1] = i; // Mirror the digit

                const curNum = Number(num.join('')); // Construct the number
                if (curNum % k === 0) { // Check divisibility by k
                    const sortedArr = Array.from(num).sort((a, b) => a - b);
                    const sortedNum = sortedArr.join(''); // Create a sorted string
                    if (was.has(sortedNum)) continue; // Skip duplicates
                    was.add(sortedNum); // Add to the set of unique numbers

                    // Count digit frequencies for combinatorics
                    const freqArr0 = Array(10).fill(0);
                    for (const digit of sortedNum) {
                        freqArr0[Number(digit)]++;
                    }
                    const freqArr = freqArr0.filter(el => el > 0); // Non-zero frequencies

                    // Calculate total variations using combinatorics
                    let variations = 1;
                    let len = n;
                    for (let i = 0; i < freqArr.length; i++) {
                        const freq = freqArr[i];
                        if (i === 0 && freqArr0[0] > 0) {
                            // No leading zeros
                            variations *= C(len - 1, freq);
                        } else {
                            variations *= C(len, freq);
                        }
                        len -= freq; // Reduce remaining length
                    }

                    total += variations; // Add to the total count
                }
            }
        } else {
            // Recursively place digits to form palindromes
            for (let i = 0; i <= 9; i++) {
                num[curDepth] = i; // Place digit at current depth
                num[n - curDepth - 1] = i; // Mirror the digit
                helper(curDepth + 1); // Recurse deeper
            }
        }
    };

    // Start constructing palindromes, ensuring no leading zeros
    for (let i = 1; i <= 9; i++) {
        num[0] = i; // First digit (non-zero)
        num[n - 1] = i; // Last digit (mirrored)

        if (maxDepth < 1) {
            // Handle edge case for very small n
            const curNum = Number(num.join(''));
            if (curNum % k === 0) {
                total++;
            }
        } else {
            helper(1); // Start recursion from depth 1
        }
    }

    return total; // Return the total count of "good" integers
};