Is Find the Count of Good Integers easy or hard?

The problem is rated Hard because it mixes multiple concepts: palindrome construction, modular arithmetic, combinatorics for counting permutations, and deduplication using hashing. The difficulty comes from recognizing that enumerating palindromes drastically reduces the search space.

Find the Count of Good Integers Python/Java solution

Typical implementations generate palindrome halves with recursion or loops, compute the full value modulo k, and store digit frequency signatures in a set or map. After collecting valid signatures, factorial-based combinatorics calculates the number of valid permutations. The same logic translates directly to Python, Java, C++, and other languages.

How to solve Find the Count of Good Integers in O(10^(n/2))?

Generate the first half of a palindrome using backtracking, mirror it to construct the full number, and compute the remainder modulo k. If the palindrome is divisible by k, store its digit frequency signature in a hash set. For each unique digit multiset, use factorial-based combinatorics to count valid n-digit permutations while excluding those that start with zero.

What is the best approach for Find the Count of Good Integers?

The most practical approach enumerates palindromes using backtracking, checks divisibility by k, and deduplicates digit multisets with a hash table. After identifying valid digit frequencies, combinatorics formulas compute how many n-digit permutations exist without leading zeros. This reduces the search space to about O(10^(n/2)) instead of all n-digit numbers.

Is Find the Count of Good Integers asked at Google/Amazon/Meta?

Problems combining combinatorics, palindrome construction, and modular arithmetic frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test enumeration reduction, hash-based deduplication, and counting permutations efficiently.

What data structure is used in Find the Count of Good Integers?

A hash table (or hash set) stores digit frequency signatures to avoid counting the same digit multiset multiple times. Factorial arrays or precomputed combinations support permutation counting, and recursion or iteration generates palindrome halves.

What is the time complexity of Find the Count of Good Integers?

The common optimized solution runs in roughly O(10^(n/2)) time because it generates only half of each palindrome and mirrors the digits. Space complexity is also around O(10^(n/2)) due to storing unique digit-frequency signatures in a hash set or map.

Description Hints 2 Solution Video 49:26

3272. Find the Count of Good Integers

Hard69.5% acceptance2 companies

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

Asked at 2 companies

Google Meta

Topics

Hints open one at a time

Hint 1

How to generate all K-palindromic strings of length n? Do we need to go through all n digits?

Hint 2

Use permutations to calculate the number of possible rearrangements.

49:26

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution