LeetCode 3272 - Find the Count of Good Integers

LeetCode Problem 3272

Difficulty: 🔴 Hard
Topics: Hash Table, Math, Combinatorics, Enumeration

Solution

Problem Understanding

The problem asks us to count n-digit integers that are "good" with respect to a given integer k. A "good" integer is one whose digits can be rearranged to form a k-palindromic integer. A k-palindromic integer is defined as an integer that satisfies two properties: it is a palindrome (reads the same forwards and backwards), and it is divisible by k.

The input consists of two integers: n, the number of digits, and k, the divisor. The output is the count of all n-digit integers that can be rearranged into a k-palindrome. The constraints tell us that n can be up to 10, and k is a single-digit integer. Because n is small, we can explore combinatorial techniques, but a naive enumeration of all n-digit integers would be inefficient for large n. Leading zeros are not allowed, either in the original number or in any rearranged palindrome.

Important edge cases include n = 1, where palindromes are single digits, and k = 1, which makes any palindrome divisible by 1. We must also handle numbers that contain zeros carefully because leading zeros in the palindrome would make them invalid.

Approaches

Brute Force

The brute-force approach would enumerate all n-digit integers. For each integer, we would generate all permutations of its digits, check if any permutation forms a palindrome, and then check if the palindrome is divisible by k. This approach is correct because it directly tests the definition of a "good" integer. However, the complexity is factorial in n due to permutations, making it infeasible for n = 10.

Optimal Approach

The key observation is that we do not need to permute all integers. Instead, we can focus on counting valid palindromes that are divisible by k, and then compute how many integers can be rearranged to form those palindromes. We can generate half of the palindrome digits (because a palindrome is symmetric) and determine the full number. Using combinatorial counts of digit frequencies, we can determine how many original integers can rearrange into each palindrome.

The steps are:

1. Generate all candidate palindromes of length n with digits 1-9 in the first position and 0-9 elsewhere.
2. Check divisibility by k.
3. Count permutations of digits that could form this palindrome using factorials, accounting for repeated digits.

This reduces the search space dramatically and avoids generating all n-digit integers explicitly.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n! * 10^n)	O(n)	Enumerate all n-digit numbers and check all permutations
Optimal	O(9 * 10^(ceil(n/2)))	O(n)	Generate half-palindromes, check k-divisibility, count rearrangements

Algorithm Walkthrough

1. Compute the length of half the palindrome, half_len = (n + 1) // 2. For odd n, the middle digit is handled separately.
2. Enumerate all digit sequences for the first half of the palindrome. The first digit cannot be zero.
3. Construct the full palindrome from the half by mirroring digits around the center.
4. Check if the full palindrome is divisible by k. If not, discard it.
5. For valid palindromes, count the number of original integers whose digits can be rearranged to form this palindrome. This uses factorial division for repeated digits.
6. Accumulate the counts to get the total number of good integers.

Why it works: Any n-digit integer that can be rearranged into a palindrome must have digits that match the palindrome's frequency distribution. By enumerating palindromes and counting possible rearrangements using combinatorics, we guarantee all "good" integers are counted exactly once.

Python Solution

from math import factorial
from collections import Counter

class Solution:
    def countGoodIntegers(self, n: int, k: int) -> int:
        def generate_half(length):
            if length == 0:
                return ['']
            if length == 1:
                return [str(d) for d in range(10)]
            prev = generate_half(length - 1)
            result = []
            for num in prev:
                for d in range(10):
                    result.append(num + str(d))
            return result
        
        def count_permutations(counter):
            total = sum(counter.values())
            res = factorial(total)
            for v in counter.values():
                res //= factorial(v)
            return res
        
        half_len = (n + 1) // 2
        total_count = 0
        for first_digit in range(1, 10):
            stack = [(str(first_digit), 1)]
            while stack:
                seq, idx = stack.pop()
                if idx == half_len:
                    # build full palindrome
                    if n % 2 == 0:
                        full = seq + seq[::-1]
                    else:
                        full = seq + seq[-2::-1]
                    if int(full) % k == 0:
                        counter = Counter(full)
                        total_count += count_permutations(counter)
                    continue
                for d in range(10):
                    stack.append((seq + str(d), idx + 1))
        return total_count

Explanation: We recursively build all valid halves of the palindrome, ensuring the first digit is not zero. For each half, we generate the full palindrome and check divisibility. For valid palindromes, we count permutations of digits using Counter and factorial math to account for repeated digits.

Go Solution

package main

import (
	"fmt"
)

func factorial(n int) int64 {
	if n == 0 || n == 1 {
		return 1
	}
	res := int64(1)
	for i := 2; i <= n; i++ {
		res *= int64(i)
	}
	return res
}

func countPermutations(counter map[int]int) int64 {
	total := 0
	for _, v := range counter {
		total += v
	}
	res := factorial(total)
	for _, v := range counter {
		res /= factorial(v)
	}
	return res
}

func buildFullPalindrome(seq []int, n int) []int {
	res := make([]int, n)
	copy(res[:len(seq)], seq)
	if n%2 == 0 {
		for i := 0; i < len(seq); i++ {
			res[n-i-1] = seq[i]
		}
	} else {
		for i := 0; i < len(seq)-1; i++ {
			res[n-i-1] = seq[i]
		}
	}
	return res
}

func countGoodIntegers(n int, k int) int64 {
	total := int64(0)
	var dfs func([]int, int)
	halfLen := (n + 1) / 2
	dfs = func(seq []int, idx int) {
		if idx == halfLen {
			full := buildFullPalindrome(seq, n)
			val := 0
			for _, d := range full {
				val = val*10 + d
			}
			if val%k == 0 {
				counter := make(map[int]int)
				for _, d := range full {
					counter[d]++
				}
				total += countPermutations(counter)
			}
			return
		}
		start := 0
		if idx == 0 {
			start = 1
		}
		for d := start; d <= 9; d++ {
			dfs(append(seq, d), idx+1)
		}
	}
	for d := 1; d <= 9; d++ {
		dfs([]int{d}, 1)
	}
	return total
}

func main() {
	fmt.Println(countGoodIntegers(3, 5)) // 27
}

Go differences: We use slices instead of strings, maps instead of Counter, and explicit int64 factorials to avoid overflow. DFS is used to build half palindromes recursively.

Worked Examples

Example 1: n = 3, k = 5

• Half length = 2
• First half sequences: 11, 12, ..., 99 (first digit != 0)
• Construct full palindromes: 111, 121, 131, ..., 999
• Check divisible by 5: 505, 515, 525, ...
• Count permutations of digits: sequences like 525 => 525, 552, 255 (3 permutations)
• Sum over all valid palindromes => 27

Example 2: n = 1, k = 4

• Single-digit palindromes: 1, 2, 3, ..., 9
• Divisible by 4: 4, 8
• Count = 2

Example 3: n = 5, k = 6

• Half length = 3
• Generate half sequences: 100 - 999
• Construct full palindrome: e.g., 12321
• Check divisible by 6
• Count permutations => 2468 total

Complexity Analysis

Measure	Complexity	Explanation
Time	O(9 * 10^(ceil(n/2)))	Enumerate first half of palindrome, which dominates the runtime
Space	O(n)	Stack or recursion depth proportional to half-length of palindrome

The time complexity is acceptable because `