Problem Informations

Problem Index: 3272
Problem Link: Find the Count of Good Integers
Topics: Hash Table, Math, Combinatorics, Enumeration

Problem Description

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 \leq n \leq 10$
$1 \leq k \leq 9$

Intuition

The problem requires counting integers with ( n ) digits that can be rearranged to form a palindrome divisible by a given ( k ). A palindrome reads the same forward and backward, and appropriate counting must handle these properties efficiently. The challenge also entails ensuring no integer has leading zeros, which further complicates the combinatorial process. The use of permutations and recursive generation of palindromic numbers while avoiding invalid leading zeros and counting distinct digit arrangements forms the core intuition behind solving this problem.

Approach

The solution utilizes a combinatorial approach with backtracking to generate potential palindromic configurations. Here’s a structured breakdown of the algorithm:

Factorial Precomputation: To efficiently compute permutations of digit arrangements, factorials up to a reasonable bound (here 14) are precomputed.
Palindromic Construction:
- A recursive method, construct_palindrome, generates all possible halfway (or complete for odd-length) palindromic configurations via backtracking.
- It sets the digits symmetrically across the center of the palindrome, ensuring first digits are non-zero by starting from 1.
Permutation Calculation:
- For each candidate palindrome, the algorithm checks how many permutations of its digits exist that do not start with zero.
- If a digit configuration can create a palindrome divisible by ( k ), permutations excluding those starting with zero are counted.
Uniqueness via Hashing:
- To avoid duplicate counting, a hash value is computed for each digit configuration. This hash reflects the unique set of digit occurrences.
- A set tracks visited configurations, preventing redundant calculations.
Recursive Base and Progression:
- Base Case: If the left index surpasses the right, the potential palindrome is complete. Its numerical validity (divisibility by ( k )) is immediately checked.
- Recursive Progression: The recursion progresses by fixing palindrome mirroring digits and extending outwards.
Result Compilation:
- The final count accumulates throughout the recursion, adding valid palindrome permutations to the answer.

This algorithm effectively navigates the constraints and properties of palindromes by integrating permutation eligibility, divisibility checks, and avoiding repetitive calculations through hashing. Each step is carefully aligned to enforce leading zero rules and modular constraints, ensuring only valid and unique ( k )-palindromic integers are counted.

Code

C++

class Solution {
    long long factorial[15] = {0};  // Precomputed factorial values
    set<long long> visited;         // Set to store unique hash values of digit counts
    vector<int> num_vec;            // Vector for constructing palindrome digits
    vector<int> digit_count;        // Vector for counting the occurrences of digits 0-9
    long long answer;               // Resulting count of good integers

    // Helper function to calculate permutations when leading zeros are present
    long long leading_zero_permutation(int n) {
        if (digit_count[0] == 0) return 0;  // No leading zero case
        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;
    }
    
    // Helper function to calculate total permutations and exclude leading zero permutations
    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);
    }
    
    // Recursive function to construct palindromes
    void construct_palindrome(int n, int k, int left, int right) {
        if (left > right) {
            // Calculate the numeric value of the palindrome
            long long num_val = 0;
            for (int elm : num_vec) {
                num_val = num_val * 10 + elm;
            }
            if (num_val % k != 0) return;  // Ensure divisibility by k

            // Count the occurrences of each digit in the palindrome
            digit_count.assign(10, 0);
            for (int i = 0; i < n; i++) {
                digit_count[num_vec[i]]++;
            }
            
            // Generate a hash value for deduplication
            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;  // Skip duplicates

            answer += calc_permutation(n);  // Increment answer by valid permutations
            visited.insert(hash_val);       // Mark this configuration as visited
            return;
        }
        
        // Ensure the first digit is nonzero
        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;  // Initialize factorial array
        factorial[1] = 1;
        for (int i = 2; i < 15; i++) {
            factorial[i] = factorial[i - 1] * i;
        }

        visited.clear();          // Clear visited set
        answer = 0;               // Reset answer
        num_vec.resize(n);        // Resize num_vec to match the number of digits
        digit_count.resize(10, 0);// Initialize digit count vector
        
        // Start constructing palindromes
        construct_palindrome(n, k, 0, n - 1);
        return answer;
    }
};

Python

class Solution:
    def __init__(self):
        self.factorial = [0] * 15  # Precomputed factorial values
        self.visited = set()       # Set to store unique hash values of digit counts
        self.num_vec = []          # List for constructing palindrome digits
        self.digit_count = []      # List for counting the occurrences of digits 0-9
        self.answer = 0            # Resulting count of good integers

    # Helper function to calculate permutations when leading zeros are present
    def leading_zero_permutation(self, n):
        if self.digit_count[0] == 0:
            return 0  # No leading zero case
        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

    # Helper function to calculate total permutations and exclude leading zero permutations
    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)

    # Recursive function to construct palindromes
    def construct_palindrome(self, n, k, left, right):
        if left > right:
            # Calculate the numeric value of the palindrome
            num_val = 0
            for elm in self.num_vec:
                num_val = num_val * 10 + elm
            if num_val % k != 0:
                return  # Ensure divisibility by k

            # Count the occurrences of each digit in the palindrome
            self.digit_count = [0] * 10
            for i in range(n):
                self.digit_count[self.num_vec[i]] += 1

            # Generate a hash value for deduplication
            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  # Skip duplicates

            self.answer += self.calc_permutation(n)  # Increment answer by valid permutations
            self.visited.add(hash_val)  # Mark this configuration as visited
            return

        # Ensure the first digit is nonzero
        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  # Initialize factorial array
        self.factorial[1] = 1
        for i in range(2, 15):
            self.factorial[i] = self.factorial[i - 1] * i

        self.visited.clear()  # Clear visited set
        self.answer = 0  # Reset answer
        self.num_vec = [0] * n  # Resize num_vec to match the number of digits
        self.digit_count = [0] * 10  # Initialize digit count list

        # Start constructing palindromes
        self.construct_palindrome(n, k, 0, n - 1)
        return self.answer

Complexity

Time complexity: The time complexity of the given algorithm is $O(10^{n/2})$.
Explanation: The construct_palindrome function recursively tries to fill in the $n$ digits from both the start and end, moving toward the center. Therefore, it effectively has $n/2$ independent positions to fill, each with a possible range of 10 digits (0 through 9), but the first digit cannot be zero unless there are no other options. This translates to a maximum of $10^{n/2}$ recursive calls. Within each recursive call, operations such as palindrome number construction, divisibility check, digit counting, and hash computation are all $O(n)$ operations. However, since these do not multiply with the exponential term, they do not change the overall exponential nature of the complexity.
Space complexity: The space complexity of the algorithm is $O(n)$.
Explanation: The primary space consumption comes from the vectors num_vec and digit_count, each of which stores data proportional to the number of digits, $n$. The factorial array, which stores a constant number of factorial values (up to 14), and the visited set for deduplication, which stores a limited number of hash values, have fixed or incidental contributions relative to the problem constraints. Thus, the space complexity is dictated primarily by $O(n)$ for num_vec and digit_count.

CS Note
中

Leetcode 3272. Find the Count of Good Integers