Problem

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.

Examples

Example 1:

1
2
3
4
5
6

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:

1
2
3
4

Input: n = 1, k = 4
Output: 2
Explanation:
The two good integers are 4 and 8.

Example 3:

1
2

Input: n = 5, k = 6
Output: 2468

Constraints:

  • 1 <= n <= 10
  • 1 <= k <= 9

Solution

Method 1 - Enumeration + Permutation and Combination

The problem revolves around counting good integers composed of n digits, where a good integer is defined as:

  1. It can be rearranged to form a k-palindromic integer.
  2. A k-palindromic integer is a number that:
    • Is a palindrome (i.e., reads the same forwards and backwards).
    • Is divisible by k.
  3. It must have no leading zeros after rearrangement.

The key insight is to break the problem into manageable sections by leveraging palindromic symmetry and efficient combinatorial calculations.

Approach

Our approach consists of the following key steps:

Step 1: Generate all valid n-digit Palindromes
  • Palindromes are symmetrical numbers. Construct them using:
    • Base digits: Starting from 10^(ceil(n/2) - 1) to 10^(ceil(n/2)), where the first half of the palindrome is iterated (e.g., abc or ab ).
    • Reflection with adjustments:
      • If n is odd, exclude the middle digit in reflection.
      • For example:
        • Odd n=5: abc|cba.
        • Even n=4: ab|ba.
Step 2: Filter k-palindromic numbers
  • Check each generated palindrome to see if it is divisible by k.
  • If it is divisible, sort its digits and store the sorted form in a Set to eliminate duplicates caused by rearrangements:
    • For example:
      • 12021 and 21012 will both sort to "01122".
Step 3: Precompute factorials
  • Precompute factorials up to n to optimise calculations for permutations and combinations.
  • Factorials help compute the number of unique ways an integer can be rearranged using its frequency counts.
Step 4: Count valid good integers
  • For each unique digit combination in the Set, compute:
    • Total permutations of the digits with:
      • Leading zeros removed.
      • Factorial division for repetitive digits (e.g., for 112, divide by 2! for the two 1s).
    • Final count:
      • Calculate valid permutations for each digit group and sum them to find the total number of good integers.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

public class Solution {

    public long countGoodIntegers(int n, int k) {
        Set<String> dict = new HashSet<>();
        int base = (int) Math.pow(10, (n - 1) / 2);
        int skip = n & 1;

        // Enumerate palindromic integers with n digits
        for (int i = base; i < base * 10; i++) {
            String s = Integer.toString(i);
            s += new StringBuilder(s).reverse().substring(skip); // Create the palindrome
            long palindromicInteger = Long.parseLong(s);

            // Check if it's k-palindromic
            if (palindromicInteger % k == 0) {
                char[] chars = s.toCharArray();
                Arrays.sort(chars); // Sort digits to create a canonical representation
                dict.add(new String(chars));
            }
        }

        // Compute factorials for permutation calculations
        long[] factorial = new long[n + 1];
        factorial[0] = 1;
        for (int i = 1; i <= n; i++) {
            factorial[i] = factorial[i - 1] * i;
        }

        long ans = 0;

        // Calculate the total good integers
        for (String s : dict) {
            int[] cnt = new int[10];
            for (char c : s.toCharArray()) {
                cnt[c - '0']++;
            }

            // Calculate permutations and combinations
            long tot = (n - cnt[0]) * factorial[n - 1]; // Remove leading zeros
            for (int x : cnt) {
                tot /= factorial[x]; // Account for repeating digits
            }
            ans += tot;
        }

        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution:
    def count_good_integers(self, n: int, k: int) -> int:
        dict_set: Set[str] = set()
        base = 10**((n - 1) // 2)
        skip = n & 1
        
        # Generate all n-digit palindromes
        for i in range(base, base * 10):
            s = str(i)
            s += s[::-1][skip:]  # Create the palindrome
            palindromic_integer = int(s)
            
            # Check if it's k-palindromic
            if palindromic_integer % k == 0:
                dict_set.add("".join(sorted(s)))  # Canonical representation
        
        # Precompute factorials for permutations and combinations
        factorials = [1] * (n + 1)
        for i in range(1, n + 1):
            factorials[i] = factorial(i)
        
        result = 0

        # Calculate total count of good integers
        for s in dict_set:
            cnt = [0] * 10
            for char in s:
                cnt[int(char)] += 1
            
            # Leading zero handling + permutation calculation
            total = (n - cnt[0]) * factorials[n - 1]
            for count in cnt:
                total //= factorials[count]
            result += total
        
        return result

Complexity

  • ⏰ Time complexity: O(10^(n/2) * n)
    • Palindrome generation: O(10^(n/2)), as only half the digit space is iterated.
    • Sorting/digit manipulation: O(n * log(n)) for each valid palindrome.
    • Permutation calculation: O(n) for each valid palindrome using precomputed factorials.
    • Overall: O(10^(n/2) * n).
  • 🧺 Space complexity: O(10^(n/2))
    • Factorial computation: O(n).
    • Palindrome storage: proportional to 10^(n/2) for valid palindromes stored.