題目資訊

題目編號: 3272
題目連結: Find the Count of Good Integers
主題: Hash Table, Math, Combinatorics, Enumeration

題目敘述

你有兩個正整數 $n$ 和 $k$。

一個整數 $x$ 被稱為 k-回文數 如果：

$x$ 是一個回文數。
$x$ 能被 $k$ 整除。

一個整數被稱為好整數如果它的數位可以重新排列成一個 k-回文數。例如，對於 $k = 2$，2020 可以重新排列成 k-回文數 2002，而 1010 無法重新排列成 k-回文數。

返回包含 $n$ 個數位的好整數的數量。

注意，任何整數不應有前導零，既不在重新排列之前也不在重新排列之後。例如，1010 不能被重新排列成 101。

範例 1:

輸入: $n = 3$, $k = 5$

輸出: 27

解釋:

一些好的整數是：

551 因為它可以重新排列形成 515。
525 因為它本身就是 k-回文數。

範例 2:

輸入: $n = 1$, $k = 4$

輸出: 2

解釋:

兩個好的整數是 4 和 8。

範例 3:

輸入: $n = 5$, $k = 6$

輸出: 2468

限制條件:

$1 \leq n \leq 10$
$1 \leq k \leq 9$

直覺

本問題要求計算在給定 ( n ) 位數下，可以重組形成能被給定 ( k ) 整除的迴文數。迴文數是指正序與反序都相同的數字，必須有效地進行計數以達成此目標。此問題的挑戰還在於確保沒有數字具有首位零，這使得組合計算更加複雜。使用排列組合和遞歸生成迴文數，避免無效的首位零，同時計算不同的數字安排，構成了解決這個問題的核心直覺。

解法

解法使用了一種結合組合計算的方式和回溯技術來生成可能的迴文配置。以下是演算法的結構化分析：

階乘預計算：為了有效地計算數字排列，預先計算到一定範圍（這裡是14）的階乘。
迴文構造：
- 使用遞歸方法 construct_palindrome 通過回溯生成所有可能的中段（或對於奇數長度為完整）迴文配置。
- 該方法將數字對稱地設置於迴文的中心兩側，確保第一個數字非零，即從1開始。
排列計算：
- 對於每個候選迴文，演算法檢查其數字排列中有多少種排列的前端未出現零。
- 若一個數字配置能產生能被 ( k ) 整除的迴文，則計數不含前端零的排列。
通過雜湊保證唯一性：
- 通過計算每個數字配置的雜湊值來避免重複計數。此雜湊值反映數字出現的唯一集合。
- 使用集合追蹤已訪問的配置，避免重複計算。
遞歸基底和進展：
- 基底情況：若左索引超過右索引，表示潛在的迴文完整。立即檢查其數值上的有效性（是否能被 ( k ) 整除）。
- 遞歸進展：通過固定迴文鏡像數字並向外延伸遞歸。
結果匯總：
- 最終的計數在整個遞歸過程中累積，將有效的迴文排列加至答案中。

此演算法有效地通過整合排列計算合法性、可被整除性檢查以及通過雜湊避免重複計算來處理迴文的約束與性質。每個步驟都小心地遵從引領零和整數模約束，確保只計算有效且唯一的 ( k )-迴文整數。

程式碼

C++

class Solution {
    long long factorial[15] = {0};  // 預先計算的階乘值
    set<long long> visited;         // 用來儲存數字計數的唯一哈希值的集合
    vector<int> num_vec;            // 用於構建迴文數字的向量
    vector<int> digit_count;        // 用於計數數位0-9出現次數的向量
    long long answer;               // 最終計算的好整數數量

    // 當有前導零的情況下計算排列數的輔助函數
    long long leading_zero_permutation(int n) {
        if (digit_count[0] == 0) return 0;  // 無前導零情況
        long long perm = factorial[n - 1];
        perm /= factorial[digit_count[0] - 1];
        for (int i = 1; i < 10; i++) {
            if (digit_count[i] != 0) {
                perm /= factorial[digit_count[i]];
            }
        }
        return perm;
    }
    
    // 計算總排列數並排除前導零排列的輔助函數
    long long calc_permutation(int n) {
        long long perm = factorial[n];
        for (int i = 0; i < 10; i++) {
            if (digit_count[i] != 0) {
                perm /= factorial[digit_count[i]];
            }
        }
        return perm - leading_zero_permutation(n);
    }
    
    // 遞歸構建迴文的函數
    void construct_palindrome(int n, int k, int left, int right) {
        if (left > right) {
            // 計算迴文的數值
            long long num_val = 0;
            for (int elm : num_vec) {
                num_val = num_val * 10 + elm;
            }
            if (num_val % k != 0) return;  // 確保能被k整除

            // 計算迴文中每個數位的出現次數
            digit_count.assign(10, 0);
            for (int i = 0; i < n; i++) {
                digit_count[num_vec[i]]++;
            }
            
            // 生成用於去重的哈希值
            long long hash_val = 0;
            for (int i = 0; i < 10; i++) {
                for (int j = 0; j < 4; j++) {
                    hash_val |= (long long)(digit_count[i] & (1 << j)) << (i * 4);
                }
            }
            if (visited.count(hash_val)) return;  // 跳過重複項

            answer += calc_permutation(n);  // 透過有效排列數增量更新答案
            visited.insert(hash_val);       // 將此配置標記為已訪問
            return;
        }
        
        // 確保首位數字不是零
        int start = (left == 0 ? 1 : 0);
        for (int i = start; i < 10; i++) {
            num_vec[left] = num_vec[right] = i;
            construct_palindrome(n, k, left + 1, right - 1);
        }
    }

public:
    long long countGoodIntegers(int n, int k) {
        factorial[0] = 1;  // 初始化階乘數組
        factorial[1] = 1;
        for (int i = 2; i < 15; i++) {
            factorial[i] = factorial[i - 1] * i;
        }

        visited.clear();          // 清空已訪問集合
        answer = 0;               // 重置答案
        num_vec.resize(n);        // 調整num_vec大小以匹配數位長度
        digit_count.resize(10, 0);// 初始化數位計數向量
        
        // 開始構建迴文
        construct_palindrome(n, k, 0, n - 1);
        return answer;
    }
};

Python

class Solution:
    def __init__(self):
        self.factorial = [0] * 15  # 預先計算的階乘值
        self.visited = set()       # 用來存儲數位計數的唯一雜湊值的集合
        self.num_vec = []          # 用於構建回文數字的列表
        self.digit_count = []      # 用於計算數字0-9出現次數的列表
        self.answer = 0            # 最終計算出的好整數數量

    # 輔助函數：計算當有前導零存在時的排列數量
    def leading_zero_permutation(self, n):
        if self.digit_count[0] == 0:
            return 0  # 無前導零的情況
        perm = self.factorial[n - 1]
        perm //= self.factorial[self.digit_count[0] - 1]
        for i in range(1, 10):
            if self.digit_count[i] != 0:
                perm //= self.factorial[self.digit_count[i]]
        return perm

    # 輔助函數：計算總排列數量並排除前導零排列
    def calc_permutation(self, n):
        perm = self.factorial[n]
        for i in range(10):
            if self.digit_count[i] != 0:
                perm //= self.factorial[self.digit_count[i]]
        return perm - self.leading_zero_permutation(n)

    # 遞迴函數：構建回文數
    def construct_palindrome(self, n, k, left, right):
        if left > right:
            # 計算回文數字的數值
            num_val = 0
            for elm in self.num_vec:
                num_val = num_val * 10 + elm
            if num_val % k != 0:
                return  # 確保能被k整除

            # 計算回文數中字的出現次數
            self.digit_count = [0] * 10
            for i in range(n):
                self.digit_count[self.num_vec[i]] += 1

            # 生成用於去重的雜湊值
            hash_val = 0
            for i in range(10):
                for j in range(4):
                    hash_val |= (self.digit_count[i] & (1 << j)) << (i * 4)
            
            if hash_val in self.visited:
                return  # 跳過重複情況

            self.answer += self.calc_permutation(n)  # 驗證排列後增加答案
            self.visited.add(hash_val)  # 標記此配置為已訪問
            return

        # 確保首位數字不是零
        start = 1 if left == 0 else 0
        for i in range(start, 10):
            self.num_vec[left] = self.num_vec[right] = i
            self.construct_palindrome(n, k, left + 1, right - 1)

    def countGoodIntegers(self, n, k):
        self.factorial[0] = 1  # 初始化階乘陣列
        self.factorial[1] = 1
        for i in range(2, 15):
            self.factorial[i] = self.factorial[i - 1] * i

        self.visited.clear()  # 清空已訪問集合
        self.answer = 0  # 重置答案
        self.num_vec = [0] * n  # 調整num_vec以符合數位數量
        self.digit_count = [0] * 10  # 初始化數字計數列表

        # 開始構建回文
        self.construct_palindrome(n, k, 0, n - 1)
        return self.answer

複雜度分析

時間複雜度: $O(10^{n/2})$
解釋: construct_palindrome 函數遞迴地嘗試從開始和結束位置填入 $n$ 個數字，向中央移動。因此，實際上有 $n/2$ 個獨立位置需要填入，每個位置有 10 個可能的數字範圍（從 0 到 9），但第一個數字不能是零，除非沒有其他選擇。這意味著最多有 $10^{n/2}$ 次遞迴調用。在每次遞迴調用中，像是構建回文數、可除性檢查、數字計數和哈希計算等操作都是 $O(n)$ 操作。然而，由於這些操作不會與指數項相乘，因此不會改變整體指數性質的複雜度。
空間複雜度: $O(n)$
解釋: 主要的空間消耗來自於 num_vec 和 digit_count 這兩個向量，這兩者儲存的資料比例與數字的數量 $n$ 成正比。factorial 陣列儲存一定數量的階乘值（最多到 14），以及用於去重的 visited 集合，儲存有限數量的哈希值，這些相對於問題限制而言有固定或偶然性的貢獻。因此，空間複雜度主要由 $O(n)$ 的 num_vec 和 digit_count 主導。

CS Note
En

Leetcode 3272. Find the Count of Good Integers

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析