Find the Count of Good Integers

Find the Count of Good Integers

What is this problem about?

The Find the Count of Good Integers interview question asks you to count how many $n$-digit integers are "good." A good integer is usually defined by two properties: it must be a palindrome of a specific length $n$, and it must be divisible by a given integer $k$. This Find the Count of Good Integers coding problem combines string symmetry with divisibility rules.

Why is this asked in interviews?

Meta and Google ask this to evaluate a candidate's ability to handle Combinatorics and Enumeration. It requires you to generate valid candidates (palindromes) and then check their properties efficiently. It tests whether you can identify that you only need to iterate through the first half of the digits to generate all possible palindromes.

Algorithmic pattern used

This problem utilizes Palindrome Generation and Frequency Analysis.

1. Generate Halves: For an $n$-digit number, iterate through all possible values for the first $ceil(n/2)$ digits.
2. Construct Palindromes: Mirror the half to form a full $n$-digit string.
3. Divisibility Check: Convert the string to a number and check if num % k == 0.
4. Count Permutations: For each valid "base" palindrome, find all unique permutations of its digits that do not have leading zeros. Use the formula: $Total! / (freq1! imes freq2! \dots)$.

Example explanation

$n=3, k=5$.

1. We need 3-digit palindromes divisible by 5.
2. Possible first digits: 5 (since a 3-digit palindrome starts and ends with the same digit, and it must end in 0 or 5 to be divisible by 5. Leading 0 is not allowed, so it must be 5).
3. Half is 5X. $X$ can be $0 \dots 9$.
4. Palindromes: 505, 515, 525... 595. All are divisible by 5.
5. Now, calculate unique permutations for each.

Common mistakes candidates make

• Leading Zeros: Forgetting to subtract permutations that start with 0 when counting "good integers."
• Brute Force: Trying to check every $n$-digit number ($10^n$). Even for $n=10$, this is impossible. You must only generate palindromes ($10^{n/2}$).
• Combinatorial Errors: Miscalculating the multinomial coefficient when handling duplicate digits.

Interview preparation tip

Practice counting "Unique Permutations of a String." This is a sub-problem in many combinatorial tasks. The formula is the total length factorial divided by the product of the factorials of each character's frequency.