Find the Count of Good Integers

Hard

#2904Time: O(10^h * n), where `h = (n+1)/2`. The loop runs `O(10^h)` times. Inside the loop, constructing the palindrome, getting the multiset key, and set insertion take `O(n)`. The final counting step also takes at most `O(10^h * n)`.Space: O(10^h * n) to store the unique multiset keys in the worst case, where `h = (n+1)/2`.

Patterns

Math Combinatorics Enumeration

Data structures

Hash Table

Prompt

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 <= n <= 10
1 <= k <= 9

Approaches

2 approaches with complexity analysis and trade-offs.

This is a highly efficient approach that directly generates the objects of interest: n-digit palindromes. It iterates through all possible first halves of an n-digit palindrome, constructs the full palindrome, and checks if it's divisible by k. The digit multisets of all such valid palindromes are stored in a set to ensure uniqueness. Finally, for each unique multiset, it calculates the number of corresponding good integers (n-digit permutations) and sums them up.

Algorithm

1. Determine the length of the first half of the palindrome, h = (n+1)/2.
1. Iterate through all possible h-digit numbers for the first half. The range is [10^(h-1), 10^h - 1].
1. For each first_half number, construct the full n-digit palindrome p.
1. If p is divisible by k, compute its digit multiset and store a canonical representation (e.g., a sorted string of its digits) in a HashSet to keep track of unique valid multisets.
1. After checking all possible first halves, iterate through the unique multisets found.
1. For each multiset, calculate the number of n-digit permutations, subtracting those that start with a zero.
1. Sum up the counts for all unique multisets to get the final result.

Walkthrough

An n-digit palindrome is uniquely determined by its first h = ceil(n/2) digits. For example, if n=5, the first 3 digits (e.g., 123) define the palindrome (12321). If n=4, the first 2 digits (e.g., 12) define the palindrome (1221). The first half must be an h-digit number, meaning its first digit cannot be zero. So, we can iterate through all numbers from 10^(h-1) to 10^h - 1 to represent all possible first halves. The algorithm proceeds as follows:

Calculate h = (n+1)/2.
Initialize a Set to store the canonical representations of digit multisets of valid k-palindromes. A canonical representation can be a sorted string of the digits.
Loop through each possible first_half number from 10^(h-1) to 10^h - 1.
Inside the loop, construct the full n-digit palindrome p.
Check if p is divisible by k.
If p % k == 0, determine its digit multiset, create a canonical representation (e.g., sort the digits and form a string), and add it to the set. Using a set automatically handles cases where different palindromes (like 1221 and 2112) might have the same multiset.
After the loop finishes, iterate through the unique multisets in the set.
For each unique multiset, calculate the number of distinct n-digit integers that can be formed from it, being careful to exclude permutations with leading zeros.
Sum these counts to get the final answer.

1import java.util.*;2 3class Solution {4    public int countGoodIntegers(int n, int k) {5        int h = (n + 1) / 2;6        long start = (long) Math.pow(10, h - 1);7        long end = (long) Math.pow(10, h) - 1;8 9        Set<String> validMultisets = new HashSet<>();10 11        for (long i = start; i <= end; i++) {12            long p = constructPalindrome(i, n);13            if (p % k == 0) {14                validMultisets.add(getMultisetKey(p));15            }16        }17 18        long totalGoodIntegers = 0;19        long[] fact = new long[n + 1];20        fact[0] = 1;21        for (int i = 1; i <= n; i++) {22            fact[i] = fact[i - 1] * i;23        }24 25        for (String multisetKey : validMultisets) {26            int[] counts = new int[10];27            for (char c : multisetKey.toCharArray()) {28                counts[c - '0']++;29            }30 31            long perms = fact[n];32            for (int count : counts) {33                perms /= fact[count];34            }35 36            if (counts[0] > 0) {37                long invalidPerms = fact[n - 1];38                invalidPerms /= fact[counts[0] - 1];39                for (int i = 1; i < 10; i++) {40                    invalidPerms /= fact[counts[i]];41                }42                perms -= invalidPerms;43            }44            totalGoodIntegers += perms;45        }46 47        return (int) totalGoodIntegers;48    }49 50    private long constructPalindrome(long firstHalf, int n) {51        String s1 = String.valueOf(firstHalf);52        String s2 = new StringBuilder(s1.substring(0, n / 2)).reverse().toString();53        return Long.parseLong(s1 + s2);54    }55 56    private String getMultisetKey(long p) {57        char[] chars = String.valueOf(p).toCharArray();58        Arrays.sort(chars);59        return new String(chars);60    }61}

Complexity

Time

O(10^h * n), where `h = (n+1)/2`. The loop runs `O(10^h)` times. Inside the loop, constructing the palindrome, getting the multiset key, and set insertion take `O(n)`. The final counting step also takes at most `O(10^h * n)`.

Space

O(10^h * n) to store the unique multiset keys in the worst case, where `h = (n+1)/2`.

Trade-offs

Pros

Very efficient as it directly generates only the necessary palindromes.
The number of palindromes to check is relatively small (9 * 10^((n+1)/2 - 1)), making it fast even for n=10.
Using a set for multisets elegantly handles duplicates.

Cons

Requires careful implementation of palindrome construction from the first half.
Space complexity depends on the number of unique valid multisets, which could be large in theory, but is manageable for the given constraints.

Solutions

Solution

1class Solution {2public3  long countGoodIntegers(int n, int k) {4    long[] fac = new long[n + 1];5    fac[0] = 1;6    for (int i = 1; i <= n; i++) {7      fac[i] = fac[i - 1] * i;8    }9    long ans = 0;10    Set<String> vis = new HashSet<>();11    int base = (int)Math.pow(10, (n - 1) / 2);12    for (int i = base; i < base * 10; i++) {13      String s = String.valueOf(i);14      StringBuilder sb = new StringBuilder(s).reverse();15      s += sb.substring(n % 2);16      if (Long.parseLong(s) % k != 0) {17        continue;18      }19      char[] arr = s.toCharArray();20      Arrays.sort(arr);21      String t = new String(arr);22      if (vis.contains(t)) {23        continue;24      }25      vis.add(t);26      int[] cnt = new int[10];27      for (char c : arr) {28        cnt[c - '0']++;29      }30      long res = (n - cnt[0]) * fac[n - 1];31      for (int x : cnt) {32        res /= fac[x];33      }34      ans += res;35    }36    return ans;37  }38}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem