Find the Count of Good Integers | Leetcode 3272

class Solution {
    #define ll long long
    ll k_palindromes = 0;
    unordered_set<ll> done;
    vector<ll> fact;

    void precomputeFactorial(int& n){
        fact[0] = 1;
        fact[1] = 1;
        for(ll i=2;i<=10;++i)
            fact[i] = i*fact[i-1];
    }
    ll countAllPermutations(vector<ll>& freq,int n){
        ll count = fact[n];
        for(int i=0;i<=9;++i)
            count /= fact[freq[i]];
        return count;
    }
    ll allArrangements(string number,int& n){
        sort(number.begin(),number.end());
        if(done.count(stoll(number)))//If already included then skip
            return 0;
        
        done.insert(stoll(number));
        //Find frequency of each digit
        vector<ll> freq(10);
        for(char& c: number)
            freq[c-'0']++;
        
        ll total_permutations = countAllPermutations(freq,n);
        ll invalid_permutations = 0;
        if(freq[0]>0){
            freq[0]--;
            invalid_permutations = countAllPermutations(freq,n-1);
        }
        return  total_permutations - invalid_permutations;
    }

    bool isKPalindrome(string& number,int& n,int& k){
        return (stoll(number)%k==0);
    }
    void generatePalindromes(int pos,int& n,string& number,int& k){
        if(pos>=(n+1)/2){
            if(isKPalindrome(number,n,k))
                k_palindromes += allArrangements(number,n);
            return;
        }

        char start = pos==0? '1':'0';
        while(start<='9'){
            number[pos]=start;
            number[n-pos-1]=start;
            generatePalindromes(pos+1,n,number,k);
            start++;
        }
        number[pos]=' ';
    }
public:
    long long countGoodIntegers(int n, int k) {
        fact = vector<ll>(11);
        precomputeFactorial(n);
        string number(n,' ');
        generatePalindromes(0,n,number,k);
        return k_palindromes;
    }
};
/*
//JAVA
import java.util.*;

class Solution {
    private long kPalindromes = 0;
    private Set<Long> done = new HashSet<>();
    private long[] fact = new long[11];

    private void precomputeFactorial(int n) {
        fact[0] = 1;
        fact[1] = 1;
        for (int i = 2; i <= 10; ++i)
            fact[i] = i * fact[i - 1];
    }

    private long countAllPermutations(int[] freq, int n) {
        long count = fact[n];
        for (int i = 0; i <= 9; ++i)
            count /= fact[freq[i]];
        return count;
    }

    private long allArrangements(String number, int n) {
        char[] numArray = number.toCharArray();
        Arrays.sort(numArray);
        String sortedNumber = new String(numArray);
        long num = Long.parseLong(sortedNumber);
        if (done.contains(num))
            return 0;

        done.add(num);
        int[] freq = new int[10];
        for (char c : sortedNumber.toCharArray())
            freq[c - '0']++;

        long totalPermutations = countAllPermutations(freq, n);
        long invalidPermutations = 0;
        if (freq[0] > 0) {
            freq[0]--;
            invalidPermutations = countAllPermutations(freq, n - 1);
        }
        return totalPermutations - invalidPermutations;
    }

    private boolean isKPalindrome(String number, int n, int k) {
        return Long.parseLong(number) % k == 0;
    }

    private void generatePalindromes(int pos, int n, StringBuilder number, int k) {
        if (pos >= (n + 1) / 2) {
            String numStr = number.toString();
            if (isKPalindrome(numStr, n, k))
                kPalindromes += allArrangements(numStr, n);
            return;
        }

        char start = (pos == 0) ? '1' : '0';
        while (start <= '9') {
            number.setCharAt(pos, start);
            number.setCharAt(n - pos - 1, start);
            generatePalindromes(pos + 1, n, number, k);
            start++;
        }
        number.setCharAt(pos, ' ');
    }

    public long countGoodIntegers(int n, int k) {
        precomputeFactorial(n);
        StringBuilder number = new StringBuilder();
        for (int i = 0; i < n; i++)
            number.append(' ');
        generatePalindromes(0, n, number, k);
        return kPalindromes;
    }
}

#Python
class Solution:
    def __init__(self):
        self.k_palindromes = 0
        self.done = set()
        self.fact = [0] * 11

    def precompute_factorial(self, n):
        self.fact[0] = 1
        self.fact[1] = 1
        for i in range(2, 11):
            self.fact[i] = i * self.fact[i - 1]

    def count_all_permutations(self, freq, n):
        count = self.fact[n]
        for i in range(10):
            count //= self.fact[freq[i]]
        return count

    def all_arrangements(self, number, n):
        sorted_num = ''.join(sorted(number))
        num = int(sorted_num)
        if num in self.done:
            return 0

        self.done.add(num)
        freq = [0] * 10
        for c in sorted_num:
            freq[int(c)] += 1

        total_permutations = self.count_all_permutations(freq, n)
        invalid_permutations = 0
        if freq[0] > 0:
            freq[0] -= 1
            invalid_permutations = self.count_all_permutations(freq, n - 1)
        return total_permutations - invalid_permutations

    def is_k_palindrome(self, number, n, k):
        return int(number) % k == 0

    def generate_palindromes(self, pos, n, number, k):
        if pos >= (n + 1) // 2:
            num_str = ''.join(number)
            if self.is_k_palindrome(num_str, n, k):
                self.k_palindromes += self.all_arrangements(num_str, n)
            return

        start = '1' if pos == 0 else '0'
        for c in range(ord(start), ord('9') + 1):
            number[pos] = chr(c)
            number[n - pos - 1] = chr(c)
            self.generate_palindromes(pos + 1, n, number, k)
        number[pos] = ' '

    def count_good_integers(self, n: int, k: int) -> int:
        self.precompute_factorial(n)
        number = [' '] * n
        self.generate_palindromes(0, n, number, k)
        return self.k_palindromes
*/