LeetCode Solutions Blog

Find the Count of Good Integers

Number: 3548

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given two positive integers n and k, count the number of n‑digit integers (with no leading zeros) that are “good.” An integer is defined as good if its digits can be rearranged into a k‑palindromic number – a palindrome that is divisible by k. For example, when k = 2, the integer 2020 is good because it can be rearranged into the palindrome 2002, which is divisible by 2; however, 1010 is not good because no rearrangement produces a valid k‑palindrome. The task is to compute the count of such good integers with exactly n digits.

Key Insights

A rearrangable palindrome can be analyzed by looking at the frequency counts of its digits (for an even‑length number, every digit must appear an even number of times; for odd‑length, exactly one digit appears an odd number of times).
The no‑leading‑zero rule must hold both in the original integer and in any rearrangement that forms a valid palindrome.
The palindrome property allows us to only “choose” the first half (and possibly the center digit) and mirror it to construct the full number.
Instead of generating every permutation, a combinatorial dynamic programming (DP) approach can count the valid arrangements, while simultaneously accumulating the modulo value of the constructed palindrome.
Since k is small (≤ 9) and n is bounded (n ≤ 10), even methods that conceptually “try” many possibilities remain feasible.

Space and Time Complexity

Time Complexity: The approach involves enumerating multiset distributions and using DP over half‑length positions; the worst‑case is exponential in n but n is at most 10, so it runs in constant time in practice. Space Complexity: O(n) for the DP state and recursion depth, bounded by a small constant given n ≤ 10.

Solution

We can solve the problem using the following strategy:

Note that any palindrome of n digits can be fully determined by its first half (for even n) or by its first half combined with a single center digit (for odd n). Let halfLen be n/2 (integer division) and let mid exist for odd n.
For each valid “half” arrangement, compute its contribution to the final palindrome number in modulo k. For position i (from 0 to halfLen–1), digit d appears in both the i‑th position from the left and the i‑th from the right. Therefore, its contribution is d * (10^(n-1-i) + 10^i) modulo k.
If n is odd, the center digit contributes d * 10^(halfLen) modulo k.
Use DP/backtracking to count the number of ways to fill the half positions from a multiset of digits, carefully enforcing that the very first selected digit is not 0.
For each multiset distribution of digits that can be rearranged into a palindrome (i.e. frequency constraints are met), combine the count of valid half permutations with the valid choices (if n is odd) for the center digit. When combining, update the modulo value and check if the overall constructed palindrome is divisible by k.
Use memoization to cache DP states. The states include the current position in half, the current accumulated modulo, and the remaining frequency counts of the digits.
Sum the counts of complete palindromes for which the final total modulo is 0.
Finally, sum over the counts across all valid distributions to return the final answer.

The key trick is breaking the problem into a half–build of the palindrome using digit multisets, while managing the “no leading zero” requirement and carrying the modulo k calculation. Because n is small, enumeration and combinatorial DP suffice even though the logic is somewhat intricate.

Code Solutions

# Python solution with detailed comments
import math
from functools import lru_cache

def countGoodIntegers(n, k):
    # Precompute powers of 10 modulo k up to n digits.
    modPow = [1] * (n+1)
    for i in range(1, n+1):
        modPow[i] = (modPow[i-1] * 10) % k

    halfLen = n // 2
    isOdd = (n % 2 != 0)
    
    # Precompute weight for each half position.
    # For a digit at position i (0-indexed from left)
    # its mirror appears at position n-1-i.
    weights = []
    for i in range(halfLen):
        weight = (modPow[n-1-i] + modPow[i]) % k
        weights.append(weight)
    # If odd, compute center digit weight.
    centerWeight = modPow[halfLen] if isOdd else None

    # DP for half part: state (pos, currentMod, freq of digits left for the half)
    # We work with a frequency tuple for digits 0-9 representing how many times each digit is available.
    # For a valid palindrome, the full frequency counts must allow half counts for the paired positions.
    @lru_cache(maxsize=None)
    def dp(pos, currentMod, freq):
        if pos == halfLen:
            # All half positions placed.
            count = 0
            if isOdd:
                # For odd length palindromes, try every possible center digit.
                for d in range(10):
                    # If the full frequency (2*freq + center) is to be valid, the center digit must come from
                    # the extra one that had odd frequency.
                    # Here, we assume that dp is called on a candidate half from an overall valid frequency distribution.
                    # We require that adding center d does not produce a leading zero in the final arrangement.
                    # No additional check on center digit is needed for leading zero.
                    newMod = (currentMod + d * centerWeight) % k
                    if newMod == 0:
                        count += 1
            else:
                count = 1 if currentMod == 0 else 0
            return count
        
        ways = 0
        # Try every digit d (0-9)
        for d in range(10):
            # At position 0, digit cannot be zero.
            if pos == 0 and d == 0:
                continue
            # Check if this digit is available in the multiset (we are building one half of the full palindrome).
            if freq[d] > 0:
                # Convert freq to list to update count.
                newFreq = list(freq)
                newFreq[d] -= 1
                newFreq = tuple(newFreq)
                # Update modulo with the contribution of this digit at position pos.
                newMod = (currentMod + d * weights[pos]) % k
                ways += dp(pos + 1, newMod, newFreq)
        return ways

    # The overall idea is to iterate over all valid ways to assign a full frequency from the n-digit number
    # that can form a palindrome.
    # Because n is small (<=10), we can enumerate each frequency distribution of digits that sum to n,
    # check if the frequency can be rearranged into a palindrome (i.e. at most one digit appears odd number of times),
    # then compute the number of distinct palindromes (by counting the arrangements in the half positions).
    total = 0
    # Create a recursive function to assign digits counts.
    def enumerateFreq(digit, remaining, currentFreq):
        nonlocal total
        if digit == 10:
            if remaining != 0:
                return
            # currentFreq is a 10-tuple representing the frequency counts of digits in the n-digit number.
            # Check palindrome property: at most one odd count.
            oddCount = sum(1 for count in currentFreq if count % 2 != 0)
            if oddCount > 1:
                return
            # Construct half frequency: for each digit, halfFreq[d] = count//2
            halfFreq = tuple(count // 2 for count in currentFreq)
            # Leading digit constraint for the final palindrome: the first digit of the full number
            # comes from the first digit of the half; if the candidate digit frequency leads to no valid starting digit, skip.
            # We require that at least one non-zero digit is available in halfFreq.
            if halfFreq[0] == 0 and sum(halfFreq[1:]) == 0:
                return
            # Count valid half arrangements using dp.
            ways = dp(0, 0, halfFreq)
            # Count the number of full arrangements corresponding to this frequency distribution multiplicatively.
            # However, if the dp already ensures no leading zero and takes into account combinatorics,
            # we can add ways directly.
            total += ways
            return
        
        # For the current digit, assign possible counts from 0 to remaining.
        for count in range(remaining + 1):
            newFreq = currentFreq + (count,)
            enumerateFreq(digit + 1, remaining - count, newFreq)

    enumerateFreq(0, n, tuple())
    return total

# Example usage:
print(countGoodIntegers(3, 5))  # Expected output: 27
print(countGoodIntegers(1, 4))  # Expected output: 2
print(countGoodIntegers(5, 6))  # Expected output: 2468