Find the Count of Good Integers

HARD

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

Approaches

Checkout 2 different approaches to solve Find the Count of Good Integers. Click on different approaches to view the approach and algorithm in detail.

Generate Palindromes and Count Permutations

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.

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.

import java.util.*;

class Solution {
    public int countGoodIntegers(int n, int k) {
        int h = (n + 1) / 2;
        long start = (long) Math.pow(10, h - 1);
        long end = (long) Math.pow(10, h) - 1;

        Set<String> validMultisets = new HashSet<>();

        for (long i = start; i <= end; i++) {
            long p = constructPalindrome(i, n);
            if (p % k == 0) {
                validMultisets.add(getMultisetKey(p));
            }
        }

        long totalGoodIntegers = 0;
        long[] fact = new long[n + 1];
        fact[0] = 1;
        for (int i = 1; i <= n; i++) {
            fact[i] = fact[i - 1] * i;
        }

        for (String multisetKey : validMultisets) {
            int[] counts = new int[10];
            for (char c : multisetKey.toCharArray()) {
                counts[c - '0']++;
            }

            long perms = fact[n];
            for (int count : counts) {
                perms /= fact[count];
            }

            if (counts[0] > 0) {
                long invalidPerms = fact[n - 1];
                invalidPerms /= fact[counts[0] - 1];
                for (int i = 1; i < 10; i++) {
                    invalidPerms /= fact[counts[i]];
                }
                perms -= invalidPerms;
            }
            totalGoodIntegers += perms;
        }

        return (int) totalGoodIntegers;
    }

    private long constructPalindrome(long firstHalf, int n) {
        String s1 = String.valueOf(firstHalf);
        String s2 = new StringBuilder(s1.substring(0, n / 2)).reverse().toString();
        return Long.parseLong(s1 + s2);
    }

    private String getMultisetKey(long p) {
        char[] chars = String.valueOf(p).toCharArray();
        Arrays.sort(chars);
        return new String(chars);
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: O(10^h * n) to store the unique multiset keys in the worst case, where `h = (n+1)/2`.

Pros and Cons

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.

Code Solutions

Checking out 4 solutions in different languages for Find the Count of Good Integers. Click on different languages to view the code.

class Solution {
public
  long countGoodIntegers(int n, int k) {
    long[] fac = new long[n + 1];
    fac[0] = 1;
    for (int i = 1; i <= n; i++) {
      fac[i] = fac[i - 1] * i;
    }
    long ans = 0;
    Set<String> vis = new HashSet<>();
    int base = (int)Math.pow(10, (n - 1) / 2);
    for (int i = base; i < base * 10; i++) {
      String s = String.valueOf(i);
      StringBuilder sb = new StringBuilder(s).reverse();
      s += sb.substring(n % 2);
      if (Long.parseLong(s) % k != 0) {
        continue;
      }
      char[] arr = s.toCharArray();
      Arrays.sort(arr);
      String t = new String(arr);
      if (vis.contains(t)) {
        continue;
      }
      vis.add(t);
      int[] cnt = new int[10];
      for (char c : arr) {
        cnt[c - '0']++;
      }
      long res = (n - cnt[0]) * fac[n - 1];
      for (int x : cnt) {
        res /= fac[x];
      }
      ans += res;
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Find the Count of Good Integers

Patterns:

MathCombinatoricsEnumeration

Data Structures:

Hash Table